Digraphs with isomorphic underlying and domination graphs: connected U G c ( d )

Kim A.S. Factor; Larry J. Langley

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 1, page 51-67
  • ISSN: 2083-5892

Abstract

top
The domination graph of a directed graph has an edge between vertices x and y provided either (x,z) or (y,z) is an arc for every vertex z distinct from x and y. We consider directed graphs D for which the domination graph of D is isomorphic to the underlying graph of D. We demonstrate that the complement of the underlying graph must have k connected components isomorphic to complete graphs, paths, or cycles. A complete characterization of directed graphs where k = 1 is presented.

How to cite

top

Kim A.S. Factor, and Larry J. Langley. "Digraphs with isomorphic underlying and domination graphs: connected $UG^c(d)$." Discussiones Mathematicae Graph Theory 27.1 (2007): 51-67. <http://eudml.org/doc/270289>.

@article{KimA2007,
abstract = {The domination graph of a directed graph has an edge between vertices x and y provided either (x,z) or (y,z) is an arc for every vertex z distinct from x and y. We consider directed graphs D for which the domination graph of D is isomorphic to the underlying graph of D. We demonstrate that the complement of the underlying graph must have k connected components isomorphic to complete graphs, paths, or cycles. A complete characterization of directed graphs where k = 1 is presented.},
author = {Kim A.S. Factor, Larry J. Langley},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination graph; domination; graph isomorphism; underlying graph; characterization},
language = {eng},
number = {1},
pages = {51-67},
title = {Digraphs with isomorphic underlying and domination graphs: connected $UG^c(d)$},
url = {http://eudml.org/doc/270289},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Kim A.S. Factor
AU - Larry J. Langley
TI - Digraphs with isomorphic underlying and domination graphs: connected $UG^c(d)$
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 1
SP - 51
EP - 67
AB - The domination graph of a directed graph has an edge between vertices x and y provided either (x,z) or (y,z) is an arc for every vertex z distinct from x and y. We consider directed graphs D for which the domination graph of D is isomorphic to the underlying graph of D. We demonstrate that the complement of the underlying graph must have k connected components isomorphic to complete graphs, paths, or cycles. A complete characterization of directed graphs where k = 1 is presented.
LA - eng
KW - domination graph; domination; graph isomorphism; underlying graph; characterization
UR - http://eudml.org/doc/270289
ER -

References

top
  1. [1] B.D. Acharya and M.N. Vartak, Open neighbourhood graphs, Indian Institute of Technology Dept. of Mathematics Research Report No. 7, Bombay-400 076, India (1973). 
  2. [2] D.B. Bergstrand and L. Friedler, Domination graphs of tournaments and other digraphs, Ars Combinatoria 74 (2005) 89-96. Zbl1078.05061
  3. [3] R.C. Brigham and R.D. Dutton, On neighbourhood graphs, J. Combin., Information & System Sciences 12 (1987) 75-85. Zbl0668.05056
  4. [4] H.H. Cho, S.R. Kim and J.R. Lundgren, Domination graphs of regular tournaments, Discrete Math. 252 (2002) 57-71, doi: 10.1016/S0012-365X(01)00289-8. Zbl0993.05106
  5. [5] H.H. Cho, F. Doherty, S.R. Kim and J.R. Lundgren, Domination graphs of regular tournaments II, Congress. Numer. 130 (1998) 95-111. Zbl0952.05052
  6. [6] C. Cocking and K.A.S. Factor, Domination-stable forms of complete biorientations of some classes of graphs, Congress. Numer. 160 (2003) 83-96. Zbl1043.05088
  7. [7] G. Exoo and F. Harary, Step graphs, J. Combin. Information & System Sciences 5 (1987) 52-53. 
  8. [8] J.D. Factor and K.A.S. Factor, Partial domination graphs of extended tournaments, Congress. Numer. 158 (2002) 119-130. Zbl1032.05099
  9. [9] K.A.S. Factor and L.J. Langley, Characterization of Digraphs with Equal Domination Graphs and Underlying Graphs, preprint (2005). Zbl1129.05016
  10. [10] K.A.S. Factor, Domination graphs of compressed tournaments, Congress. Numer. 157 (2002) 63-78. Zbl1029.05119
  11. [11] D.C. Fisher, D. Guichard, S.K. Merz and J.R. Lundgren, Domination graphs with nontrivial components, Graphs and Combin. 17 (2001) 227-228, doi: 10.1007/s003730170036. Zbl0989.05081
  12. [12] D.C. Fisher, D. Guichard, J.R. Lundgren, S.K. Merz and K.B. Reid, Domination graphs with 2 or 3 nontrivial components, Bulletin of the ICA 40 (2004) 67-76. Zbl1037.05037
  13. [13] D.C. Fisher, D. Guichard, J.R. Lundgren, S.K. Merz and K.B. Reid, Domination graphs of tournaments with isolated vertices, Ars Combin. 66 (2003) 299-311. Zbl1072.05555
  14. [14] D.C. Fisher, J.R. Lundgren, S.K. Merz and K.B. Reid, Connected domination graphs of tournaments, JCMCC 31 (1999) 169-176. Zbl0942.05028
  15. [15] D.C. Fisher, J.R. Lundgren, S.K. Merz and K.B. Reid, The domination and competition graphs of a tournament, J. Graph Theory 29 (1998) 103-110, doi: 10.1002/(SICI)1097-0118(199810)29:2<103::AID-JGT6>3.0.CO;2-V Zbl0919.05024
  16. [16] D.C. Fisher, J.R. Lundgren, S.K. Merz and K.B. Reid, Domination graphs of tournaments and digraphs, Congress. Numer. 108 (1995) 97-107. Zbl0904.05051
  17. [17] H.J. Greenburg, J.R. Lundgren and J.S. Maybee, The inversion of 2-step graphs, J. Combin. Information & System Sciences 8 (1983) 33-43. Zbl0631.05044
  18. [18] J.R. Lundgren, J.S. Maybee and C.W. Rasmussen, Interval competition graphs of symmetric digraphs, Discrete Math. 119 (1993) 113-123, doi: 10.1016/0012-365X(93)90121-9. Zbl0790.05036
  19. [19] J.R. Lundgren, J.S. Maybee and C.W. Rasmussen, An application of generalized competition graphs to the channel assignment problem, Congress. Numer. 71 (1990) 217-224. Zbl0747.05093

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.