Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
integral sum graph; saturated vertex; edge-chromatic number
integral sum graph; saturated vertex; edge-chromatic number
Summary:
As introduced by F. Harary in 1994, a graph $ G$ is said to be an $integral$ $ sum$ $ graph$ if its vertices can be given a labeling $f$ with distinct integers so that for any two distinct vertices $u$ and $v$ of $G$, $uv$ is an edge of $G$ if and only if $ f(u)+f(v)=f(w)$ for some vertex $w$ in $G$. \endgraf We prove that every integral sum graph with a saturated vertex, except the complete graph $K_3$, has edge-chromatic number equal to its maximum degree. (A vertex of a graph $G$ is said to be {\it saturated} if it is adjacent to every other vertex of $G$.) Some direct corollaries are also presented.
References:
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. Macmillan, London (1976). MR 0411988
[2] Chartrand, G., Lesniak, L.: Graphs and Digraphs, 2nd ed. Wadsworth., Belmont (1986). MR 0834583 | Zbl 0666.05001
[3] Chen, Z.: Integral sum graphs from identification. Discrete Math. 181 (1998), 77-90. DOI 10.1016/S0012-365X(97)00046-0 | MR 1600747 | Zbl 0902.05064
[4] Chen, Z.: On integral sum graphs. Discrete Math. 306 (2006), 19-25 (It first appeared in The Ninth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms and Applications, 11 pp. (electronic), Electron. Notes Discrete Math., 11, Elsevier, Amsterdam, 2002.). MR 2202070 | Zbl 1084.05058
[5] Ellingham, M. N.: Sum graphs from trees. Ars Combin. 35 (1993), 335-349. MR 1220532 | Zbl 0779.05042
[6] Gallian, J.: A dynamic survey of graph labeling. Electronic J. Combinatorics 15 (2008). MR 1668059
[7] Harary, F.: Sum graphs and difference graphs. Congr. Numer. 72 (1990), 101-108. MR 1041811 | Zbl 0691.05038
[8] Harary, F.: Sum graphs over all the integers. Discrete Math. 124 (1994), 99-105. DOI 10.1016/0012-365X(92)00054-U | MR 1258846 | Zbl 0797.05069
[9] He, W., Wang, L., Mi, H., Shen, Y., Yu, X.: Integral sum graphs from a class of trees. Ars Combinatoria 70 (2004), 197-205. MR 2023075 | Zbl 1092.05059
[10] Imrich, W., Klavar, S.: Product Graphs. John Wiley & Sons, New York (2000). MR 1788124
[11] Liaw, S.-C., Kuo, D., Chang, G.: Integral sum numbers of Graphs. Ars Combin. 54 (2000), 259-268. MR 1742421 | Zbl 0993.05123
[12] Mahmoodian, E. S.: On edge-colorability of Cartesian products of graphs. Canad. Math. Bull. 24 (1981), 107-108. DOI 10.4153/CMB-1981-017-9 | MR 0611218 | Zbl 0473.05030
[13] Pyatkin, A. V.: Subdivided trees are integral sum graphs. Discrete Math. 308 (2008), 1749-1750. DOI 10.1016/j.disc.2006.12.006 | MR 2392615 | Zbl 1144.05058
[14] Sharary, A.: Integral sum graphs from complete graphs, cycles and wheels. Arab Gulf Sci. Res. 14-1 (1996), 1-14. MR 1394997 | Zbl 0856.05088
[15] Thomassen, C.: Hajós conjecture for line graphs. J. Combin. Theory Ser. B 97 (2007), 156-157. DOI 10.1016/j.jctb.2006.03.006 | MR 2278130 | Zbl 1114.05041
Search
Partner of
