| Title:
|
On integral sum graphs with a saturated vertex (English) |
| Author:
|
Chen, Zhibo |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
60 |
| Issue:
|
3 |
| Year:
|
2010 |
| Pages:
|
669-674 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
integral sum graph |
| Keyword:
|
saturated vertex |
| Keyword:
|
edge-chromatic number |
| MSC:
|
05C15 |
| MSC:
|
05C78 |
| idZBL:
|
Zbl 1224.05439 |
| idMR:
|
MR2672408 |
| . |
| Date available:
|
2010-07-20T17:08:40Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140597 |
| . |
| Reference:
|
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications.Macmillan, London (1976). MR 0411988 |
| Reference:
|
[2] Chartrand, G., Lesniak, L.: Graphs and Digraphs, 2nd ed.Wadsworth., Belmont (1986). Zbl 0666.05001, MR 0834583 |
| Reference:
|
[3] Chen, Z.: Integral sum graphs from identification.Discrete Math. 181 (1998), 77-90. Zbl 0902.05064, MR 1600747, 10.1016/S0012-365X(97)00046-0 |
| Reference:
|
[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.). Zbl 1084.05058, MR 2202070 |
| Reference:
|
[5] Ellingham, M. N.: Sum graphs from trees.Ars Combin. 35 (1993), 335-349. Zbl 0779.05042, MR 1220532 |
| Reference:
|
[6] Gallian, J.: A dynamic survey of graph labeling.Electronic J. Combinatorics 15 (2008). MR 1668059 |
| Reference:
|
[7] Harary, F.: Sum graphs and difference graphs.Congr. Numer. 72 (1990), 101-108. Zbl 0691.05038, MR 1041811 |
| Reference:
|
[8] Harary, F.: Sum graphs over all the integers.Discrete Math. 124 (1994), 99-105. Zbl 0797.05069, MR 1258846, 10.1016/0012-365X(92)00054-U |
| Reference:
|
[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. Zbl 1092.05059, MR 2023075 |
| Reference:
|
[10] Imrich, W., Klavar, S.: Product Graphs.John Wiley & Sons, New York (2000). MR 1788124 |
| Reference:
|
[11] Liaw, S.-C., Kuo, D., Chang, G.: Integral sum numbers of Graphs.Ars Combin. 54 (2000), 259-268. Zbl 0993.05123, MR 1742421 |
| Reference:
|
[12] Mahmoodian, E. S.: On edge-colorability of Cartesian products of graphs.Canad. Math. Bull. 24 (1981), 107-108. Zbl 0473.05030, MR 0611218, 10.4153/CMB-1981-017-9 |
| Reference:
|
[13] Pyatkin, A. V.: Subdivided trees are integral sum graphs.Discrete Math. 308 (2008), 1749-1750. Zbl 1144.05058, MR 2392615, 10.1016/j.disc.2006.12.006 |
| Reference:
|
[14] Sharary, A.: Integral sum graphs from complete graphs, cycles and wheels.Arab Gulf Sci. Res. 14-1 (1996), 1-14. Zbl 0856.05088, MR 1394997 |
| Reference:
|
[15] Thomassen, C.: Hajós conjecture for line graphs.J. Combin. Theory Ser. B 97 (2007), 156-157. Zbl 1114.05041, MR 2278130, 10.1016/j.jctb.2006.03.006 |
| . |
