✦ LIBER ✦

Integral distance graphs

✍ Scribed by Chen, Jer-Jeong; Chang, Gerard J.; Huang, Kuo-Ching

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 90 KB
Volume: 25
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199708)25:4<287::aid-jgt6>3.0.co;2-g

No coin nor oath required. For personal study only.

✦ Synopsis

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 when |D| is finite. Exact values of χ(G, D) are also determined for some D with |D| = 3.

📜 SIMILAR VOLUMES

Every Graph Is an Integral Distance Grap

Every Graph Is an Integral Distance Graph in the Plane

✍ Hiroshi Maehara; Katsuhiro Ota; Norihide Tokushige 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 290 KB

We prove that every finite simple graph can be drawn in the plane so that any two vertices have an integral distance if and only if they are adjacent. The proof is constructive.

Orientation distance graphs

✍ Gary Chartrand; David Erwin; Michael Raines; Ping Zhang 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB

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 pairwi

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