On a conjecture concerning the petersen graph

Robertson has conjectured that if a graph G is
# 3-connected and internally-4-connected;
# girth is 5;
# every cycle of length greater than 5 has a chord. Then G is the Petersen graph.
An internally 4-connected graph is a 3-connected graph where in which the only vertex cut of size three are the neighborhood of a vertex. A chord is an edge joining two nodes that are not adjacent in the cycle.; the girth of a graph is the length of a shortest cycle contained in the graph. Therefore a graph with a girth greater than 5 is a graph in which the length of the shortest cycle is at least 5.
Donald Nelson of Middle Tennessee State University, Michael D. Plummer of Vanderbilt University,Neil Robertson of Ohio State University, and Xiaoya Zha of Middle Tennessee State University prove this conjecture in the special case where the graphs involved are also cubic. The name of this article was titled, "On a conjecture concerning the Petersen graph" and was published January 19, 2011;
The counter-example first starts with a frame graph G that is isomorphic to the Petersen graph minus two edges. Twenty-one vertices is then added to the graph G. Matching edges are then added to some of the graph G. Four copies of the Heawood graph (3-connected, internally-4-connected, bipartite, and has a girth of six) is then connected to the twenty-one added vertices of G. The resulting graph has a girth of five, 3-connected,and every odd cycle of length greater than 5 has a chord.; Thus proving Robertson's Conjecture is true for many cases, but not all.

Main Menu

See Also

Main Menu