On integral sum graphs with a saturated vertex

Zhibo Chen

Czechoslovak Mathematical Journal (2010)

  • Volume: 60, Issue: 3, page 669-674
  • ISSN: 0011-4642

Abstract

top
As introduced by F. Harary in 1994, a graph G is said to be an i n t e g r a l s u m g r a p h if its vertices can be given a labeling f with distinct integers so that for any two distinct vertices u and v of G , u v is an edge of G if and only if f ( u ) + f ( v ) = f ( w ) for some vertex w in G . 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 saturated if it is adjacent to every other vertex of G .) Some direct corollaries are also presented.

How to cite

top

Chen, Zhibo. "On integral sum graphs with a saturated vertex." Czechoslovak Mathematical Journal 60.3 (2010): 669-674. <http://eudml.org/doc/38034>.

@article{Chen2010,
abstract = {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$. 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 saturated if it is adjacent to every other vertex of $G$.) Some direct corollaries are also presented.},
author = {Chen, Zhibo},
journal = {Czechoslovak Mathematical Journal},
keywords = {integral sum graph; saturated vertex; edge-chromatic number; integral sum graph; saturated vertex; edge-chromatic number},
language = {eng},
number = {3},
pages = {669-674},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On integral sum graphs with a saturated vertex},
url = {http://eudml.org/doc/38034},
volume = {60},
year = {2010},
}

TY - JOUR
AU - Chen, Zhibo
TI - On integral sum graphs with a saturated vertex
JO - Czechoslovak Mathematical Journal
PY - 2010
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 60
IS - 3
SP - 669
EP - 674
AB - 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$. 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 saturated if it is adjacent to every other vertex of $G$.) Some direct corollaries are also presented.
LA - eng
KW - integral sum graph; saturated vertex; edge-chromatic number; integral sum graph; saturated vertex; edge-chromatic number
UR - http://eudml.org/doc/38034
ER -

References

top
  1. Bondy, J. A., Murty, U. S. R., Graph Theory with Applications, Macmillan, London (1976). (1976) MR0411988
  2. Chartrand, G., Lesniak, L., Graphs and Digraphs, 2nd ed, Wadsworth., Belmont (1986). (1986) Zbl0666.05001MR0834583
  3. Chen, Z., 10.1016/S0012-365X(97)00046-0, Discrete Math. 181 (1998), 77-90. (1998) Zbl0902.05064MR1600747DOI10.1016/S0012-365X(97)00046-0
  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.). (2006) Zbl1084.05058MR2202070
  5. Ellingham, M. N., Sum graphs from trees, Ars Combin. 35 (1993), 335-349. (1993) Zbl0779.05042MR1220532
  6. Gallian, J., A dynamic survey of graph labeling, Electronic J. Combinatorics 15 (2008). (2008) MR1668059
  7. Harary, F., Sum graphs and difference graphs, Congr. Numer. 72 (1990), 101-108. (1990) Zbl0691.05038MR1041811
  8. Harary, F., 10.1016/0012-365X(92)00054-U, Discrete Math. 124 (1994), 99-105. (1994) Zbl0797.05069MR1258846DOI10.1016/0012-365X(92)00054-U
  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. (2004) Zbl1092.05059MR2023075
  10. Imrich, W., Klavar, S., Product Graphs, John Wiley & Sons, New York (2000). (2000) MR1788124
  11. Liaw, S.-C., Kuo, D., Chang, G., Integral sum numbers of Graphs, Ars Combin. 54 (2000), 259-268. (2000) Zbl0993.05123MR1742421
  12. Mahmoodian, E. S., 10.4153/CMB-1981-017-9, Canad. Math. Bull. 24 (1981), 107-108. (1981) Zbl0473.05030MR0611218DOI10.4153/CMB-1981-017-9
  13. Pyatkin, A. V., 10.1016/j.disc.2006.12.006, Discrete Math. 308 (2008), 1749-1750. (2008) Zbl1144.05058MR2392615DOI10.1016/j.disc.2006.12.006
  14. Sharary, A., Integral sum graphs from complete graphs, cycles and wheels, Arab Gulf Sci. Res. 14-1 (1996), 1-14. (1996) Zbl0856.05088MR1394997
  15. Thomassen, C., 10.1016/j.jctb.2006.03.006, J. Combin. Theory Ser. B 97 (2007), 156-157. (2007) Zbl1114.05041MR2278130DOI10.1016/j.jctb.2006.03.006

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.