12
$\begingroup$

I am interested in regular graphs in which every edge lies in a triangle.

For 3-regular graphs, only the complete graph $K_4$ has this property, so there's not much to see here.

For 4-regular graphs, there are more graphs, including some infinite families, but few enough and slowly-growing enough that I have some wild hope of a characterisation.

The numbers on 5, 6, ..., 17 vertices are

1, 1, 2, 2, 3, 3, 4, 8, 11, 18, 35, 57 and 106,

which is tiny compared to the total number of 4-regular graphs.

For smaller numbers of vertices there are likely to be numbers of graphs that "just happen" to have every edge in a triangle, but at some stage I am hoping they will fall into some infinite families for which one might get at least a qualitative description.

I have searched "the literature" (i.e. tried MathSciNet and Google) and cannot find any results along these lines which surprised me a bit. But perhaps it is just impossible and those numbers just keep growing...

So my question is:

Does anyone know any results or have any ideas pertaining to regular graphs, in particular 4-regular graphs, with every edge lying in a triangle?

EDIT: I think that Florian Pfender (see comment below) may have basically found the solution. All of the graphs that I have computed (on up to 17 vertices) are either:

(a) The Cayley graph Cay$(Z_n; \{ \pm 1, \pm 2 \})$ ("the square of a cycle")

(b) The linegraph of a cubic graph, or

(c) have an edge $xy$ such that the closed neighbourhood of $x$ is equal to the closed neighbourhood of $y$

This latter condition means that the two vertices $x$, $y$ have exactly three common neighbours, say $a$, $b$ and $c$. So we can reduce to a smaller graph by deleting $x$ and $y$ and adding a triangle on $a$, $b$, $c$ perhaps at the expense of introducing multiple edges.

Last thing that remains is to show that when this "reduction process" is completed, the resulting graph is just the line-multigraph of a cubic-multigraph, which is what Florian implied.

I am hopeful of a genuine result here.

(Then on to 5-regular graphs....)

FINAL EDIT: August 2013 - This question has now generated a paper containing the genuine result that I was hopeful for. See http://arxiv.org/abs/1308.0081 and https://symomega.wordpress.com/2013/08/02/regular-graphs-triangles-and-mathoverflow/.

Thanks MathOverflow!

$\endgroup$
9
  • 3
    $\begingroup$ The following easy construction provides a bunch of 4-regular graphs with each edge in a triangle: Start with a 3-regular graph. Join midpoints of edges to all midpoints of the four adjacent edges and delete the original graph. $\endgroup$ Jan 3, 2012 at 8:17
  • $\begingroup$ You just mean the linegraph, right? $\endgroup$ Jan 3, 2012 at 8:55
  • $\begingroup$ Indeed (I forgot its name). $\endgroup$ Jan 3, 2012 at 9:34
  • 4
    $\begingroup$ Do you have any connected examples which you can not get as follows: a) take a square of a cycle, or b) start with a line-multigraph of a 3-regular multigraph (i.e., parallel edges in the original yield parallel edges in the line graph). Then replace a number of your triangles which responded to vertices of the line graph original by $K_{3,1,1}$. If you want a simple graph, you have to perform that last operation at least once for every multiple edge... $\endgroup$ Jan 3, 2012 at 11:41
  • $\begingroup$ One small comment. A random regular graph of valency $k$ has few short cycles, so you'd expect the proportion of 4-regular graphs that have a triangle on each edge to go to zero as the number of vertices increases. $\endgroup$ Jan 3, 2012 at 13:46

1 Answer 1

7
$\begingroup$

yes, it feels like one could proof my characterization along the following lines:

  • If the graph does not contain $K_4^-$, then it is a line graph of a 3-regular graph.

  • Now continue with a copy of $K_4^-$. The two vertices of degree three must each be incident to another edge. If these two edges meet, then we can reduce the whole structure to a triangle like you describe (my $K_{3,1,1}$).

  • If the two edges do not meet, then they each must lie in a triangle, so there need to be edges from their endpoints to the vertices of degree 2 in the $K_4^-$. If both these edges meet in the same vertex, we again have a structure we can reduce to a triangle (a triangle in the line graph original, which we can contract keeping 3-regularity).

  • So we are left with the case where the two edges go to different sides of the $K_4^-$, and again we have two vertices of degree 3 to work with. If these two vertices are connected, then we have a $K_4$ with two triangles attached to it which we can get from the multi-line-graph of edge-doubleedge-edge by $K_{3,1,1}$ing one of the triangles (or alternatively, we can reduce the whole graph by contracting the whole structure to one vertex).

  • If these two vertices are not connected, then each must lie in a triangle with the neighboring vertex of degree 2, and this process will go on until the two sides meet in a cycle, in which case you got your square of a cycle.

$\endgroup$
3
  • $\begingroup$ I'll accept that as pretty much completely answering the question, as there doesn't seem to be much left other than filling in minor details. Two questions: how on earth did you jump from the limited information given in the initial question and prior comments to the rather precise question you asked that essentially contained the answer. Secondly: what about 5-regular? $\endgroup$ Jan 4, 2012 at 11:03
  • $\begingroup$ @gordon - At one: I essentially did exactly what I wrote up now on my whiteboard before posting that first comment. I just did not think hard enough about it to be convinced enough that it had no essential hole to post it as answer. But a little more musing plus you checking your small examples convinced me. At two: I have not thought about it yet... $\endgroup$ Jan 4, 2012 at 11:20
  • $\begingroup$ So it seems I overlooked one little building block in my characterization. Whenever there is a $K_4$ you can replace it by a 4-Wheel without harm. But this should be it. $\endgroup$ Jan 4, 2012 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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