✦ LIBER ✦

Orientation distance graphs

✍ Scribed by Gary Chartrand; David Erwin; Michael Raines; Ping Zhang

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 194 KB
Volume: 36
Category: Article
ISSN: 0364-9024
DOI: 10.1002/1097-0118(200104)36:4<230::aid-jgt1008>3.0.co;2-#

No coin nor oath required. For personal study only.

✦ Synopsis

For two nonisomorphic orientations D and D H of a graph G, the orientation distance d o (D,D H ) between D and D H is the minimum number of arcs of D whose directions must be reversed to produce an orientation isomorphic to D H . The orientation distance graph h o (G) of G has the set y(G) of pairwise nonisomorphic orientations of G as its vertex set and two vertices D and D H of h o (G) are adjacent if and only if d o (D,D H ) 1. For a nonempty subset S of y(G), the orientation distance graph h o (S) of S is the induced subgraph hS i of h o (G). A graph H is an orientation distance graph if there exists a graph G and a set S y (G) such that h o (S) is isomorphic to H. In this case, H is said to be an orientation distance graph with respect to G. This paper deals primarily with orientation distance graphs with respect to paths. For every integer n ! 4, it is shown that h o (P n ) is Hamiltonian if and only if n is even. Also, the orientation distance graph of a path of odd order is bipartite. Furthermore, every tree is an orientation distance graph with respect to some path, as is every cycle, and for n ! 3 the clique number of h o (P n ) is 2 if n is odd and is 3 otherwise.

📜 SIMILAR VOLUMES

Integral distance graphs

✍ Chen, Jer-Jeong; Chang, Gerard J.; Huang, Kuo-Ching 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB

Suppose D is a subset of all positive integers. The distance graph G(Z, D) with distance set D is the graph with vertex set Z, and two vertices x and y are adjacent if and only if |x -y| ∈ D. This paper studies the chromatic number χ(Z, D) of G(Z, D). In particular, we prove that χ(Z, D) ≤ |D| + 1 w

Distance Graphs andT-Coloring

✍ Gerard J Chang; Daphne D.-F Liu; Xuding Zhu 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 126 KB

We discuss relationships among T-colorings of graphs and chromatic numbers, fractional chromatic numbers, and circular chromatic numbers of distance graphs. We first prove that for any finite integral set T that contains 0, the asymptotic T-coloring ratio R(T ) is equal to the fractional chromatic n

Distance Biregular Bipartite Graphs

✍ C. Delorme 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 392 KB

We describe here some properties of a class of graphs which extends the class of distance regular graphs: our graphs are bipartite and for cach vertex there exists an intersection array depending on the stable component of the vertex. Thus our graphs arc to distance regular graphs as bipartite regul

Novel graph distance matrix

✍ Milan Randić; Tomaž Pisanski; Marjana Novič; Dejan Plavšić 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 390 KB

## Abstract We have introduced novel distance matrix for graphs, which is based on interpretation of columns of the adjacency matrix of a graph as a set of points in __n__‐dimensional space, __n__ being the number of vertices in the graph. Numerical values for the distances are based on the Euclide

Hamiltonian graphs involving distances

✍ Guantao Chen; R. H. Schelp 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB

## Abstract Let __G__ be a graph of order __n__. We show that if __G__ is a 2‐connected graph and max{__d(u), d(v)__} + |__N(u)__ U __N(v)__| ≥ __n__ for each pair of vertices __u, v__ at distance two, then either __G__ is hamiltonian or G 3K~n/3~ U T~1~ U T~2~, where n  O (mod 3), and __T__~1~ a

Pancyclic oriented graphs

✍ Zeng Min Song 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 324 KB

## Abstract Let __D__ be an oriented graph of order __n__ ≧ 9 and minimum degree __n__ − 2. This paper proves that __D__ is pancyclic if for any two vertices __u__ and __v__, either __uv__ ≅ __A(D)__, or __d__~__D__~^+^(__u__) + __d__~__D__~^−^(__v__) ≧ __n__ − 3.