Name
Abstract | ||
|---|---|---|
Robertson has conjectured that the only 3-connected, internally 4-connected graph of girth 5 in which every odd cycle of length greater than 5 has a chord is the Petersen graph. We prove this conjecture in the special case where the graphs involved are also cubic. Moreover, this proof does not require the internal-4-connectivity assumption. An example is then presented to show that the assumption of internal 4-connectivity cannot be dropped as an hypothesis in the original conjecture. We then summarize our results aimed toward the solution of the conjecture in its original form. In particular, let G be any 3-connected internally-4-connected graph of girth 5 in which every odd cycle of length greater than 5 has a chord. If C is any girth cycle in G then N(C)\V(C) cannot be edgeless, and if N(C)\V (C) contains a path of length at least 2, then the conjecture is true. Consequently, if the conjecture is false and H is a counterexample, then for any girth cycle C in H, N(C)\V (C) induces a nontrivial matching M together with an independent set of vertices. Moreover, M can be partitioned into (at most) two disjoint non-empty sets where we can precisely describe how these sets are attached to cycle C. |
Year | Venue | DocType |
|---|---|---|
2011 | ELECTRONIC JOURNAL OF COMBINATORICS | Journal |
Volume | Issue | ISSN |
18.0 | 1.0 | 1077-8926 |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Donald Nelson | 1 | 32 | 2.85 |
| Michael D. Plummer | 2 | 446 | 62.78 |
| Neil Robertson | 3 | 18 | 1.78 |
| Xiaoya Zha | 4 | 104 | 20.82 |