×

On the vertex-distinguishing proper edge coloring of composition of complete graph and star. (English) Zbl 1296.05081

Summary: A proper \(k\)-edge coloring of a simple graph \(G\) is called \(k\)-vertex-distinguishing proper edge coloring (\(k\)-VDPEC) if for any two distinct vertices \(u\) and \(v\) of \(G\), the set of colors assigned to edges incident to \(u\) differs from the set of colors assigned to edges incident to \(v\). The minimum number of colors required for a vertex-distinguishing proper edge coloring of \(G\), denoted by \(\chi_s^\prime(G)\), is called the vertex-distinguishing proper edge chromatic number. For \(p\geqslant 2\) and \(q\geqslant 4\), we will obtain vertex-distinguishing proper edge chromatic number of composition of complete graph \(K_p\) with order \(p\) and star \(S_q\) with order \(q\), which is \(pq\).

MSC:

05C15 Coloring of graphs and hypergraphs
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer London · Zbl 1134.05001
[2] Burris, A. C., Vertex-distinguishing edge-colorings [D] (1993), Memphis State University, Ph.D. Dissertation
[3] Balister, P. N.; Riordan, O. M.; Schelp, R. H., Vertex-distinguishing edge colorings of graphs, J. Graph Theory, 42, 2, 95-109 (2003) · Zbl 1008.05067
[4] Burris, A. C.; Schelp, R. H., Vertex-distinguishing proper edge-colorings, J. Graph Theory, 26, 2, 73-82 (1997) · Zbl 0886.05068
[5] Bazgan, C.; Harkat-Benhamdine, A.; Hao, Li; Woźniak, M., On the vertex-distinguishing proper edge colorings of graphs, J. Comb. Theory, 75, 2, 288-301 (1999) · Zbl 0932.05036
[6] Horňák, M.; Soták, R., Observability of complete multipartite graphs with equipotent parts, Ars Comb., 41, 289-301 (1995) · Zbl 0841.05032
[7] Chen, Xiang-en; Gao, Yuping, Vertex-distinguishing proper edge-coloring chromatic numbers of the composition of two graphs [J], J. Jilin Univ. China, 49, 2, 207-212 (2011) · Zbl 1249.05116
[8] Dénes, J.; Keedwell, A. D., Latin Squares and Applications (1974), Academic Press: Academic Press New York-London · Zbl 0283.05014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.