Name
Abstract | ||
|---|---|---|
For n@?N and D@?N, the distance graph P\"n^D has vertex set {0,1,...,n-1} and edge set {ij|0@?i,j@?n-1,|j-i|@?D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs. A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set D of order at least 2, there is a constant c\"D such that the greatest common divisor of the integers in D is 1 if and only if for every n, P\"n^D has a component of order at least n-c\"D if and only if for every n=c\"D+3, P\"n^D has a cycle of order at least n-c\"D. Furthermore, we discuss some consequences and variants of this result. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.disc.2010.07.020 | Discrete Mathematics |
Keywords | Field | DocType |
circulant graph,we discuss some consequences and variants of this result. keywords. circulant graph,distance graph,hamilto- nian path,hamiltonian path,hamiltonian cycle,connectivity,graph connectivity,greatest common divisor | Discrete mathematics,Combinatorics,Circulant graph,Hamiltonian path,Vertex (graph theory),Chordal graph,Cycle graph,Circulant matrix,Regular graph,Greatest common divisor,Mathematics | Journal |
Volume | Issue | ISSN |
310 | 23 | Discrete Mathematics |
Citations | PageRank | References |
4 | 0.49 | 28 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lucia Draque Penso | 1 | 196 | 20.46 |
| Dieter Rautenbach | 2 | 946 | 138.87 |
| Jayme Luiz Szwarcfiter | 3 | 618 | 95.79 |