Orientation distance graphs revisited

• Autorzy: Wayne Goddard , Kiran Kanakadandi
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

orientation; distance graph; arc reversal

Kategorie tematyczne

• 05C12: Distance in graphs
• 05C62: Graph representations (geometric and intersection representations, etc.) {For graph drawing, see also }
• 05C20: Directed graphs (digraphs), tournaments

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2007
• Tom: 27
• Numer: 1
• Strony: 125-136

Daty

wydano

2007

otrzymano

2006-01-20

poprawiono

2006-10-17

Twórcy

autor

Wayne Goddard

• Department of Computer Science, Clemson University, Clemson, SC 29634-1906, USA

autor

Kiran Kanakadandi

• Department of Computer Science, Clemson University, Clemson, SC 29634-1906, USA

Bibliografia

• [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:4<230::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.

Identyfikatory

DOI

10.7151/dmgt.1349