关于积图点可区别边染色的若干结论

Abstract

Abstract: A proper edge coloring of graph G is called vertex-distinguishing if the set of colors meets to vertex u differs from the set of colors meets to vertex v for any two distinct vertices u and v. The minimum number k for which there exists vertex distinguishing proper edge coloring using k colors is called the vertex distinguishing proper edge chromatic number. In this paper, we will obtain a conclusion of vertex-distinguishing edge coloring of product graph by using the method of construction, and get some results of the vertex-distinguishing edge chromatic numbers of product graphs, then obtain vertex-distinguishing edge chromatic numbers of 25 product graphs, which satisfy the conjecture on VDECC.

Key words: product graph, join-graph, vertex-distinguishing edge coloring, vertex-distinguishing edge chromatic number

CLC Number:

O157.5

MA Gang, MA Xiaomin, YE Jianhua, MA Shaoxian. Some conclusions of vertex-distinguishing edge coloring of product graph[J]. Operations Research Transactions, 2013, 17(3): 108-114.

References

Bazgan C, Harkat-Benhamdine A, Li H, et al. On the vertex-distinguishing proper edge-colorings of graphs [J]. J of Combine Theory (Ser B), 1999, 75: 288-301.
Burris A C, Schelp R H. Vertex-distinguishing proper edge-colorings [J]. J of Graph Theory, 1997, 26(2): 73-82.
Zhang Z F, Li J W, Chen X E, et al. D(\beta)-vertex-distinguishing proper edge-coloring of graphs [J]. Acta Mathematica Sinica (Chinese Ser), 2006, 49(3): 703-708.
Zhang Z F, Liu L Z, Wang J F. Adjacent strong edge coloring of graphs [J]. Applied Mathematics Letters, 2002, 15: 623-626.
Zhang Z F, Li M C, Yao B, et al. On the vertex distinguishing equitable edge-coloring of graphs [J]. ARS Combinatoria, 2008, 86: 193-200.
Chen X E, Gao Y P. Vertex-distinguishing proper edge-coloring chromatic numbers of the composition of two graphs [J]. J of Jilin University (Science ed.), 2011, 49(2): 207-212.
Rudasova J, Sotak R. Vertex-distinguishing proper edge coloring of some regular graphs [J]. Discrete Mathematics, 2008, 308(5/6): 795-802．
Ma G, Ma S X, Zhang Z F. On the vertex-distinguishing edge chromatic number of P_m W_n [J]. J of Lanzhou University (Natural Sciences), 2007, 43(2): 103-106.
Zhang Z F, Li J W, Zhao CC, et al. On the vertex-distinguishing-equitable edge chromatic of some join-graphs [J]. Acta Mathematica Sinica (Chinese Ser), 2007, 50(1): 197-204.
Wang Z W, Zhang Z F, Yan L H. Vertex-distinguishing edge chromatic number of P_m P_n [J]. J of Lanzhou University (Natural Sciences), 2005, 41(6): 100-101.
Tian S L, Chen P. On the vertex-distinguishing edge colorings of some product graphs [J]. J of Shandong University (Science ed.), 2006, 41(4): 53-56.
Yap H P. Total Colorings of Graphs [M]. Lecture Notes in Mathematics, 1623, Berlin: Springer, 1996.
Bondy J A, Murty U S R. Graph Theory with Applications [M]. New York: The Macmillan Press Ltd, 1976.

[1]	HU Xiaochen, HE Weili, HAO Rongxia. Balanced judicious partitions of graphs with $\Delta($G$)-\delta($G$)\leq$2 [J]. Operations Research Transactions, 2015, 19(1): 108-116.
[2]	SUN Lin, LUO Zhaoyang. Edge colourings of embedded special graphs [J]. Operations Research Transactions, 2015, 19(1): 125-130.
[3]	SONG Sulin, LIN Limei, ZHOU Shuming. The t/k-diagnosability and diagnosis algorithm of Pancake networks [J]. Operations Research Transactions, 2014, 18(4): 65-77.
[4]	LIN Yishu, LIU Yan. Bandwidth sum with an edge added [J]. Operations Research Transactions, 2014, 18(4): 105-110.
[5]	CHEN Lin, HUANG Qiongxiang. Tricyclic graphs with exactly two Q-main eigenvalues [J]. Operations Research Transactions, 2014, 18(3): 13-32.
[6]	DING Lushun, WANG Guanghui, YAN Jin. The properly colored paths and cycles for the triangle-free graphs [J]. Operations Research Transactions, 2014, 18(3): 116-120.
[7]	DUAN Huiming, ZENG Bo, DOU Zhi. On connected three multiply K_{n}-residual graphs [J]. Operations Research Transactions, 2014, 18(2): 59-68.
[8]	OUYANG Zhangdong, HUANG Yuanqiu. On the crossing number of products of K_3,3 with S_n [J]. Operations Research Transactions, 2014, 18(2): 69-76.
[9]	SHAN Erfang, YE Tingting. Clique-coloring numbers of some product graphs [J]. Operations Research Transactions, 2013, 17(4): 103-108.
[10]	ZHOU Zhidong,WANG Jing. On the crossing numbers of W₆*S_n [J]. Operations Research Transactions, 2013, 17(2): 10-18.

Some conclusions of vertex-distinguishing edge coloring of product graph

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 10

Recommended Articles

Metrics

Comments