Difference labelling of cacti

Martin Sonntag

Discussiones Mathematicae Graph Theory (2003)

  • Volume: 23, Issue: 1, page 55-65
  • ISSN: 2083-5892

Abstract

top
A graph G is a difference graph iff there exists S ⊂ IN⁺ such that G is isomorphic to the graph DG(S) = (V,E), where V = S and E = i,j:i,j ∈ V ∧ |i-j| ∈ V. It is known that trees, cycles, complete graphs, the complete bipartite graphs K n , n and K n , n - 1 , pyramids and n-sided prisms (n ≥ 4) are difference graphs (cf. [4]). Giving a special labelling algorithm, we prove that cacti with a girth of at least 6 are difference graphs, too.

How to cite

top

Martin Sonntag. "Difference labelling of cacti." Discussiones Mathematicae Graph Theory 23.1 (2003): 55-65. <http://eudml.org/doc/270668>.

@article{MartinSonntag2003,
abstract = {A graph G is a difference graph iff there exists S ⊂ IN⁺ such that G is isomorphic to the graph DG(S) = (V,E), where V = S and E = i,j:i,j ∈ V ∧ |i-j| ∈ V. It is known that trees, cycles, complete graphs, the complete bipartite graphs $K_\{n,n\}$ and $K_\{n,n-1\}$, pyramids and n-sided prisms (n ≥ 4) are difference graphs (cf. [4]). Giving a special labelling algorithm, we prove that cacti with a girth of at least 6 are difference graphs, too.},
author = {Martin Sonntag},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph labelling; difference graph; cactus},
language = {eng},
number = {1},
pages = {55-65},
title = {Difference labelling of cacti},
url = {http://eudml.org/doc/270668},
volume = {23},
year = {2003},
}

TY - JOUR
AU - Martin Sonntag
TI - Difference labelling of cacti
JO - Discussiones Mathematicae Graph Theory
PY - 2003
VL - 23
IS - 1
SP - 55
EP - 65
AB - A graph G is a difference graph iff there exists S ⊂ IN⁺ such that G is isomorphic to the graph DG(S) = (V,E), where V = S and E = i,j:i,j ∈ V ∧ |i-j| ∈ V. It is known that trees, cycles, complete graphs, the complete bipartite graphs $K_{n,n}$ and $K_{n,n-1}$, pyramids and n-sided prisms (n ≥ 4) are difference graphs (cf. [4]). Giving a special labelling algorithm, we prove that cacti with a girth of at least 6 are difference graphs, too.
LA - eng
KW - graph labelling; difference graph; cactus
UR - http://eudml.org/doc/270668
ER -

References

top
  1. [1] D. Bergstrand, F. Harary, K. Hodges, G. Jennings, L. Kuklinski and J. Wiener, The sum number of a complete graph, Bull. Malaysian Math. Soc. (Second Series) 12 (1989) 25-28. Zbl0702.05072
  2. [2] D. Bergstrand, F. Harary, K. Hodges, G. Jennings, L. Kuklinski and J. Wiener, Product graphs are sum graphs, Math. Mag. 65 (1992) 262-264, doi: 10.2307/2691455. Zbl0785.05075
  3. [3] G.S. Bloom and S.A. Burr, On autographs which are complements of graphs of low degree, Caribbean J. Math. 3 (1984) 17-28. Zbl0574.05040
  4. [4] G.S. Bloom, P. Hell and H. Taylor, Collecting autographs: n-node graphs that have n-integer signatures, Annals N.Y. Acad. Sci. 319 (1979) 93-102, doi: 10.1111/j.1749-6632.1979.tb32778.x. Zbl0484.05059
  5. [5] R.B. Eggleton and S.V. Gervacio, Some properties of difference graphs, Ars Combin. 19 (A) (1985) 113-128. Zbl0562.05026
  6. [6] M.N. Ellingham, Sum graphs from trees, Ars Combin. 35 (1993) 335-349. Zbl0779.05042
  7. [7] S.V. Gervacio, Which wheels are proper autographs?, Sea Bull. Math. 7 (1983) 41-50. Zbl0524.05054
  8. [8] R.J. Gould and V. Rödl, Bounds on the number of isolated vertices in sum graphs, in: Y. Alavi, G. Chartrand, O.R. Ollermann and A.J. Schwenk, ed., Graph Theory, Combinatorics, and Applications 1 (Wiley, New York, 1991), 553-562. Zbl0840.05042
  9. [9] T. Hao, On sum graphs, J. Combin. Math. and Combin. Computing 6 (1989) 207-212. Zbl0701.05047
  10. [10] F. Harary, Sum graphs and difference graphs, Congressus Numerantium 72 (1990) 101-108. Zbl0691.05038
  11. [11] F. Harary, Sum graphs over all the integers, Discrete Math. 124 (1994) 99-105, doi: 10.1016/0012-365X(92)00054-U. Zbl0797.05069
  12. [12] F. Harary, I.R. Hentzel and D.P. Jacobs, Digitizing sum graphs over the reals, Caribb. J. Math. Comput. Sci. 1, 1 & 2 (1991) 1-4. Zbl0835.05075
  13. [13] N. Hartsfield and W.F. Smyth, The sum number of complete bipartite graphs, in: R. Rees, ed., Graphs and Matrices (Marcel Dekker, New York, 1992), 205-211. Zbl0791.05090
  14. [14] N. Hartsfield and W.F. Smyth, A family of sparse graphs of large sum number, Discrete Math. 141 (1995) 163-171, doi: 10.1016/0012-365X(93)E0196-B. Zbl0827.05048
  15. [15] M. Miller, J. Ryan and W.F. Smyth, The sum number of the cocktail party graph, Bull. Inst. Comb. Appl. 22 (1998) 79-90. Zbl0894.05048
  16. [16] M. Miller, Slamin, J. Ryan and W.F. Smyth, Labelling wheels for minimum sum number, J. Combin. Math. and Combin. Comput. 28 (1998) 289-297. Zbl0918.05091
  17. [17] W.F. Smyth, Sum graphs of small sum number, Coll. Math. Soc. János Bolyai, 60. (Sets, Graphs and Numbers, Budapest, 1991) 669-678. Zbl0792.05120
  18. [18] W.F. Smyth, Sum graphs: new results, new problems, Bulletin of the ICA 2 (1991) 79-81. Zbl0828.05054
  19. [19] W.F. Smyth, Addendum to: 'Sum graphs: new results, new problems', Bulletin of the ICA 3 (1991) 30. Zbl0828.05055

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.