1
$\begingroup$

Cubic graphs (graphs in which every vertex has valency 3) cannot be trees, so they contain a lot of cycles. Some of these cycles have length divisible by 3 (e.g. triangles, hexagons, nonagons etc).

In a generic cubic graph some of these cycles will have chords (edges connecting non-adjacent vertices in the cycle) and some won't. My interest is in graph in which every cycle of length divisible by 3 has a chord. In particular such a graph can contain no triangles as these never have chords.

I constructed some examples, all of which were bipartite. However I don't see any natural reason why such a graph should necessarily be bipartite so my question is:

Does anyone know an example of a non-bipartite cubic graph in which every cycle of length divisible by 3 has a chord?

$\endgroup$
  • $\begingroup$ Vincent-- My previous answer (if you read it) turned out to be equivalent to yours below. Please check out the edited version of my answer which contains a six vertex example. Thanks. $\endgroup$ – coffeemath May 7 '16 at 9:02
1
$\begingroup$

I think I found an example, but I would be happy if someone could help me check if it really is one:

enter image description here

More examples are still welcome of course.

$\endgroup$
  • 1
    $\begingroup$ Your graph is a prism graph with parameter 5 (i.e. two pentagons with corresponding vertices joined). It is not bipartite because it has a 5-cycle. It has $4$ 6-cycles containing any particular vertex, and each has a chord. $\endgroup$ – Robert Israel May 6 '16 at 23:18
  • $\begingroup$ It also has $9$-cycles, but since removing a single vertex still leaves some $4$-cycles, all $9$-cycles have chords. So yes, this is really an example. $\endgroup$ – Robert Israel May 6 '16 at 23:31
  • $\begingroup$ Sorry, that should be $3$ (unordered) $6$-cycles. Each $6$-cycle consists of two adjacent $4$-cycles formed by two adjacent sides of one pentagon, the corresponding sides of the other pentagon, and the edges joining them. $\endgroup$ – Robert Israel May 6 '16 at 23:48
  • 1
    $\begingroup$ Moreover, seeing as it has $<12$ nodes, it can't possibly have an induced 9-cycle. This is another way to prove @RobertIsrael's statement. $\endgroup$ – Rosie F Feb 23 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.