Geodesic
Orientation distance graphs revisited
Discussiones Mathematicae. Graph Theory, Tome 27 (2007) no. 1, pp. 125-136
Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

The orientation distance graph ₒ(G) of a graph G is defined as the graph whose vertex set is the pair-wise non-isomorphic orientations of G, and two orientations are adjacent iff the reversal of one edge in one orientation produces the other. Orientation distance graphs was introduced by Chartrand et al. in 2001. We provide new results about orientation distance graphs and simpler proofs to existing results, especially with regards to the bipartiteness of orientation distance graphs and the representation of orientation distance graphs using hypercubes. We provide results concerning the orientation distance graphs of paths, cycles and other common graphs.
Keywords: orientation, distance graph, arc reversal 
@article{DMGT_2007_27_1_a10,
     author = {Goddard, Wayne and Kanakadandi, Kiran},
     title = {Orientation distance graphs revisited},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {125--136},
     year = {2007},
     volume = {27},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2007_27_1_a10/}
}
TY  - JOUR
AU  - Goddard, Wayne
AU  - Kanakadandi, Kiran
TI  - Orientation distance graphs revisited
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2007
SP  - 125
EP  - 136
VL  - 27
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2007_27_1_a10/
LA  - en
ID  - DMGT_2007_27_1_a10
ER  - 
%0 Journal Article
%A Goddard, Wayne
%A Kanakadandi, Kiran
%T Orientation distance graphs revisited
%J Discussiones Mathematicae. Graph Theory
%D 2007
%P 125-136
%V 27
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2007_27_1_a10/
%G en
%F DMGT_2007_27_1_a10
Goddard, Wayne; Kanakadandi, Kiran. Orientation distance graphs revisited. Discussiones Mathematicae. Graph Theory, Tome 27 (2007) no. 1, pp. 125-136. http://geodesic.mathdoc.fr/item/DMGT_2007_27_1_a10/

[1] G. Chartrand, D. Erwin, M. Raines and P. Zhang, Orientation distance graphs, J. Graph Theory 34 (2001) 230-241, doi: 10.1002/1097-0118(200104)36:4230::AID-JGT1008>3.0.CO;2-#

[2] K. Kanakadandi, On Orientation Distance Graphs, M. Sc. thesis, (Clemson University, Clemson, 2006).

[3] M. Livingston and Q.F. Stout, Embeddings in hypercubes, Math. Comput. Modelling 11 (1988) 222-227, doi: 10.1016/0895-7177(88)90486-4.

[4] B. McKay's Digraphs page, at: http://cs.anu.edu.au/∼bdm/data/digraphs.html.

[5] Jeb F. Willenbring at Sloane's 'The Online Encyclopedia of Integer Sequences' located at: http://www.research.att.com/projects/OEIS?Anum=A053656.

[6] B. Zelinka, The distance between various isomorphisms of a graph, Math. Slovaka 38 (1988) 19-25.