Difference labelling of digraphs

Martin Sonntag

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 3, page 509-527
  • ISSN: 2083-5892

Abstract

top
A digraph G is a difference digraph iff there exists an S ⊂ N⁺ such that G is isomorphic to the digraph DD(S) = (V,A), where V = S and A = {(i,j):i,j ∈ V ∧ i-j ∈ V}.For some classes of digraphs, e.g. alternating trees, oriented cycles, tournaments etc., it is known, under which conditions these digraphs are difference digraphs (cf. [5]). We generalize the so-called source-join (a construction principle to obtain a new difference digraph from two given ones (cf. [5])) and construct a difference labelling for the source-join of an even number of difference digraphs. As an application we obtain a sufficient condition guaranteeing that certain (non-alternating) trees are difference digraphs.

How to cite

top

Martin Sonntag. "Difference labelling of digraphs." Discussiones Mathematicae Graph Theory 24.3 (2004): 509-527. <http://eudml.org/doc/270712>.

@article{MartinSonntag2004,
abstract = {A digraph G is a difference digraph iff there exists an S ⊂ N⁺ such that G is isomorphic to the digraph DD(S) = (V,A), where V = S and A = \{(i,j):i,j ∈ V ∧ i-j ∈ V\}.For some classes of digraphs, e.g. alternating trees, oriented cycles, tournaments etc., it is known, under which conditions these digraphs are difference digraphs (cf. [5]). We generalize the so-called source-join (a construction principle to obtain a new difference digraph from two given ones (cf. [5])) and construct a difference labelling for the source-join of an even number of difference digraphs. As an application we obtain a sufficient condition guaranteeing that certain (non-alternating) trees are difference digraphs.},
author = {Martin Sonntag},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph labelling; difference digraph; oriented tree; graph labeling},
language = {eng},
number = {3},
pages = {509-527},
title = {Difference labelling of digraphs},
url = {http://eudml.org/doc/270712},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Martin Sonntag
TI - Difference labelling of digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 3
SP - 509
EP - 527
AB - A digraph G is a difference digraph iff there exists an S ⊂ N⁺ such that G is isomorphic to the digraph DD(S) = (V,A), where V = S and A = {(i,j):i,j ∈ V ∧ i-j ∈ V}.For some classes of digraphs, e.g. alternating trees, oriented cycles, tournaments etc., it is known, under which conditions these digraphs are difference digraphs (cf. [5]). We generalize the so-called source-join (a construction principle to obtain a new difference digraph from two given ones (cf. [5])) and construct a difference labelling for the source-join of an even number of difference digraphs. As an application we obtain a sufficient condition guaranteeing that certain (non-alternating) trees are difference digraphs.
LA - eng
KW - graph labelling; difference digraph; oriented tree; graph labeling
UR - http://eudml.org/doc/270712
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. 19A (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] S.V. Gervacio, Difference graphs, in: Proc. of the Second Franco-Southeast Asian Math. Conf., Univ. of the Philippines, May 17-June 5, 1982. 
  9. [9] 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-Intersci. Publ., Wiley, New York, 1991) 553-562. Zbl0840.05042
  10. [10] T. Hao, On sum graphs, J. Combin. Math. and Combin. Computing 6 (1989) 207-212. Zbl0701.05047
  11. [11] F. Harary, Sum graphs and difference graphs, Congress. Numer. 72 (1990) 101-108. Zbl0691.05038
  12. [12] F. Harary, Sum graphs over all the integers, Discrete Math. 124 (1994) 99-105, doi: 10.1016/0012-365X(92)00054-U. Zbl0797.05069
  13. [13] 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
  14. [14] 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
  15. [15] 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
  16. [16] 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
  17. [17] 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
  18. [18] 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
  19. [19] W.F. Smyth, Sum graphs: new results, new problems, Bulletin of the ICA 2 (1991) 79-81. Zbl0828.05054
  20. [20] W.F. Smyth, Addendum to: ``Sum graphs: new results, new problems'', Bulletin of the ICA 3 (1991) 30. Zbl0828.05055
  21. [21] M. Sonntag, Difference labelling of cacti, Discuss. Math. Graph Theory 23 (2003) 55-65, doi: 10.7151/dmgt.1185. Zbl1054.05090
  22. [22] M. Sonntag, Difference labelling of the generalized source-join of digraphs, Preprint Series of TU Bergakademie Freiberg, Faculty of Mathematics and Computer Science, Preprint 2003-03 (2003) 1-18, ISSN 1433-9307. 
  23. [23] M. Sonntag and H.-M. Teichert, Sum numbers of hypertrees, Discrete Math. 214 (2000) 285-290, doi: 10.1016/S0012-365X(99)00307-6. Zbl0943.05071
  24. [24] M. Sonntag and H.-M. Teichert, On the sum number and integral sum number of hypertrees and complete hypergraphs, Discrete Math. 236 (2001) 339-349, doi: 10.1016/S0012-365X(00)00452-0. Zbl0995.05106
  25. [25] H.-M. Teichert, The sum number of d-partite complete hypergraphs, Discuss. Math. Graph Theory 19 (1999) 79-91, doi: 10.7151/dmgt.1087. Zbl0933.05104
  26. [26] H.-M. Teichert, Classes of hypergraphs with sum number 1, Discuss. Math. Graph Theory 20 (2000) 93-104, doi: 10.7151/dmgt.1109. 
  27. [27] H.-M. Teichert, Sum labellings of cycle hypergraphs, Discuss. Math. Graph Theory 20 (2000) 255-265, doi: 10.7151/dmgt.1124. Zbl0982.05070
  28. [28] H.-M. Teichert, Summenzahlen und Strukturuntersuchungen von Hypergraphen (Berichte aus der Mathematik, Shaker Verlag Aachen, 2001). 

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.