Lower and upper bound on defining spectrum of regular graphs
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
The defining number d_c(G) of a graph G = (V,E) properly colored with c ≥Χ(G) colors, is the least number of vertices of G to which colors must be assigned in order that this assignment be uniquely extendable to a vertex coloring of G. Let F be a family of k-regular graphs on n vertices and let any graph G in F be properly coloring with c ≥Χ(G) colors. A de¯ning spectrum of F with c colors is Spec_c(F) = [수식]. The sharp lower and upper bound of Spec_c(F) of k-regular graphs, k∈{2, 3} and (Χ(G)≤c≤ k+1)are obtained. For any k, it is obtained a sharp lower bound for Spec_k(F') where F' is a family of connected k-regular graphs.
Abstract
The defining number d_c(G) of a graph G = (V,E) properly colored with c ≥Χ(G) colors, is the least number of vertices of G to which colors must be assigned in order that this assignment be uniquely extendable to a vertex coloring of G. Let F be a family of k-regular graphs on n vertices and let any graph G in F be properly coloring with c ≥Χ(G) colors. A de¯ning spectrum of F with c colors is Spec_c(F) = [수식]. The sharp lower and upper bound of Spec_c(F) of k-regular graphs, k∈{2, 3} and (Χ(G)≤c≤ k+1)are obtained. For any k, it is obtained a sharp lower bound for Spec_k(F') where F' is a family of connected k-regular graphs.
참고문헌 (15)
- P. Adams, "Smallest defining sets of some STS(19)", J. Combin. Math. Combin. Comput, 38, pp.225~230 (2001)
- R. Bean, "Closing a gap in the spectrum of critical sets", Aus-tralasian Journal of Combinatorics, 22, pp.191~200 (2000)
- D. Donovan, "Towards the spectrum of critical sets", Australasian Journal of Combinatorics, 21, pp.107~130 (2000)
- A.D. keedwell, "Critical sets for Latin squares, graphs and block designs: a survey, Festschrift for C. St. J. A., Nash-Williams", Congr. Numer, 113, pp.231~245 (1996)
- M. Mahdian, "A characterization of uniquely 2-list col-orable graphs", Ä Ars Combin, 51, pp.295~305 (1999)
- E.S. Mahmoodian, "On defining numbers of vertex coloring of regular graphs", 16th British Combinatorial Conference, 통권 : 197, pp.543~554 (1999), Discrete Math.
- E.S. Mahmoodian, "Critical sets in back circulant Latin rectangles", Australasian Journal of Combinatorics, 16, pp.45~50 (1997)
- D.A. Mojdeh, "Defining sets in (proper) vertex colorings of the Cartesian product of a cycle with a complete graph", Discussiones Mathematicae Graph Theory, 26(1), pp.59~72 (2006)
- D.A. Mojdeh, "On conjecture on the defining set of vertex graph colorings", Australasian Journal of Combinatorics, 34, pp.153~160 (2006)
- D.A. Mojdeh, "On the strong defining spectrum of k-regular graphs", Italian Journal of Pure and Applied Mathematics, (23), pp.161~172 (2007)
- D.A.Mojdeh, "Graphs K1?4;5;K1?5;4;K1?4;4;K2;3;4 have the property M", Ars Combi-natoria, 84(3), pp.171~190 (2007)
- D.A. Mojdeh, "On the defining number of (2n - 2)-vertex colorings of Kn x Kn", Bulletin of the Iranian Mathe-matical Society, 31(1), pp.49~61 (2005)
- D.A.Mojdeh, "Critical sets in Latin squares given that they are symmetric", Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat, 18, pp.3845~ (2007)
- D.A. Mojdeh, "Defining number in Harary graphs", Applied Mathematics Letters, 22, pp.922~926 (2009)
- M. Zaker, "Greedy de¯ning sets of graphs", Australas. J. Combin, 23, pp.231~235 (2001)