7
$\begingroup$

What are all 4-regular graphs such that every edge in the graph lies in a unique-4 cycle?

Among all such graphs, if we impose a further restriction that any two 4-cycles in the graph have at most one vertex in common, then can we characterize them in some way?

When is it possible to draw such a graph on a plane such that every 4-cycle is of the form: (a,c)-(b,c)-(b,d)-(a,d)-(a,c) for some a,b,c,d ?

$\endgroup$
6
  • 2
    $\begingroup$ If two edge-disjoint 4-cycles share two vertices then every edge of those 4-cycles is in 3 different 4-cycles, so your second condition is not an additional restriction. This seems to be an easy case check (there are only two ways you can possibly produce "extra" 4-cycles): could you possibly say something about where the problem comes from? $\endgroup$
    – Ben Barber
    Nov 18, 2014 at 11:48
  • 1
    $\begingroup$ @BenBarber What about the graph on {1,2,3,4,5,6} with the two cycles 1234 and 2536? They are edge-disjoint but share two vertices, and there are no other 4-cycles... $\endgroup$
    – verret
    Nov 18, 2014 at 12:11
  • $\begingroup$ @verret Yes, you're right. So the two problems are different. $\endgroup$
    – Ben Barber
    Nov 18, 2014 at 12:18
  • $\begingroup$ How many such graphs have you found, dass? $\endgroup$ Nov 19, 2014 at 4:04
  • 1
    $\begingroup$ Do you require the graph to be finite? $\endgroup$ Nov 19, 2014 at 13:40

5 Answers 5

4
$\begingroup$

There should be lots of these, even with the second condition. So many that I can't imagine a classification. I'll call a $4$-cycle a square.

One construction is as follows: Start with an appropriate connected graph such that

  • Each edge is on a unique square
  • All vertices have degree $2$ or $4$.
  • Two $4$-cycles have at most one vertex in common.

Then identify various degree $2$ vertices in pairs without making any new squares. So appropriate means you can do this. For example take an $N$ cycle for $N$ not too small, and attach a square to each edge. You could even take several of these and glue them together at vertices (in a sort of tree structure.) Here is a $12$-cycle decorated with squares and an extra square glued on just to show that we could grow this out in a wild variety of ways. I think in my identification of degree two vertices I did not create any new squares.enter image description here


The examples below are included because they look nice and are already in the comments. The graph at the top right meets my three conditions if the two red edges are deleted. I am confident that the degree $2$ vertices could be identified in pairs without creating any new $4$-cycles.

With the red edges one has four vertices of degree $3$ along with two edges not in a square. One could take a mirror image of that graph and add $4$ more edges to connect them, create two more squares and bring the degrees up (there are also easier remedies such as using two more edges to make a square with the red ones.)

I previously had a claim about the graph with the octagons which was too optimistic.It has $42$ edges missing and I won't specify how to draw them. In each half (ignoring the two curved edges) there are $22$ deficient edges which do not belong to a square and connect vertices of degree $3.$ I thought that one could connect corresponding degree $3$ vertices in each half. I now see that that would put the edge $AD$ on the left into two squares. I've indicated a different match for edge $CD$ and imagine that it is not hard, with a little care, to match up deficient edges on the left with those on the right to create just enough squares. I don't think one needs to preserve orientation. The bottom (fragment of a) graph could probably be treated similarly. One could even try to match up deficient edges without adding any new vertices. enter image description here

$\endgroup$
7
  • $\begingroup$ I don't understand this construction. In the top-left graph, the long edges connecting the "diamonds" don't appear to be in a 4-cycle and in the bottom graph the edges separating a 12-gon from a hexagon also don't seem to be. What am I missing? $\endgroup$ Nov 19, 2014 at 19:03
  • $\begingroup$ @Gordon, you aren't. Aaron is. However, there are chains of partial octahedra, drum graphs, and ways of stitching these together that supports Aaron's main contention. I agree that no nice classification is apparent. The best is to take a collection of squares, divide the vertices into certain pairs, and identify the pairs, taking care not to introduce more 4-cycles in the process. $\endgroup$ Nov 19, 2014 at 19:14
  • $\begingroup$ I just deleted a comment regarding partial octahedra, and I may need to revise my above comment similarly, since edge cycle uniqueness is not present in such chains. $\endgroup$ Nov 19, 2014 at 19:22
  • $\begingroup$ @GordonRoyle My intention with the octagon graph was to take two copies and connect degree $3$ vertices between halves putting the lonely edges into squares. I now see that my plane (connect corresponding vertices) was too hasty. I still think it could be done, but I'll leave it open. $\endgroup$ Nov 19, 2014 at 23:43
  • 2
    $\begingroup$ @Aaron : You mean 12 vertices, and yes it is the smallest and there is one more on that size that isn't planar. $\endgroup$ Nov 20, 2014 at 3:04
3
$\begingroup$

The number of vertices $n$ must be even or the number of 4-cycles is not an integer. The number of simple connected quartic graphs with the first condition is 0 for $n<12$ and $2,4,25,459$ for $n=12,14,16,18$. One of those on 12 vertices is the cuboctahedron.

After the cuboctahedron, the next 3-connected planar quartic graph with the first property has 20 vertices and there are 2 with 24 vertices.

This construction may be useful: A quartic graph with $n$ vertices and the first property has $n/2$ 4-cycles. Make a new graph $H$ with the 4-cycles of $G$ as vertices and an edge wherever two 4-cycles meet at a vertex. You get a quartic multigraph with half the number of vertices, simple if $G$ also satisfies the second property. To get back from $H$ to $G$ you need to choose a cyclic order of the edges around each vertex, which is similar to embedding it on an orientable surface except that reversing the order at some vertices doesn't change the result. This operation is related to the medial graph construction. It would probably not be hard to characterise when the medial graph of an embedded quartic graph has the required properties.

$\endgroup$
3
  • $\begingroup$ Is there any advantage to viewing the graph as some sort of medial graph, rather than just the line graph of a quartic graph with a matching arbitrarily removed from each 4-clique? Medial graphs are associated with embeddings and I can't see how dragging embeddings into things helps in this case? If the base quartic graph has girth at least five, then as Flo observed, the choice of matching to remove from each clique really is arbitrary, but not so for lower girths. $\endgroup$ Nov 20, 2014 at 13:06
  • $\begingroup$ @GordonRoyle The word mediant does not need to be mentioned but is helpful for visualizing at least some examples. It comes down to the difference between carefully putting in a $4$-cycle for each vertex and just putting in $K_4$s then carefully changing each to a $4$-cycle. I can see small girth examples where nothing works. Are there any where something works but it isn't immediate what does? $\endgroup$ Nov 20, 2014 at 16:56
  • $\begingroup$ @Gordon : While I'm not sure it helps, it does provide geometric terminology like "face". For example, in the 3-connected case at least, it may be necessary and sufficient that $H$ has no faces of size 2 or 4. (I didn't try to prove that rigorously.) If true, it is a neat way to say which 4-cycles in $H$ are ok. $\endgroup$ Nov 20, 2014 at 21:46
1
$\begingroup$

Consider two labeled squares, vertices on one labeled from the abcd alphabet, the other labeled from 1234. We are going to identify one or more pairs of vertices while maintaining the constraint that induced edges are not identified as well as not identifying vertices labeled from the same alphabet.

It is clear that there are 16 ways to make one pair of vertices. Once one such pair is made, there are for each pair precisely 4 ways to make a second disjoint pair. Making a third pair violates the edge identification condition. So there are 48 distinct ways (after removing duplicated efforts) to identify two labeled squares.

The idea now is to make a brute force enumeration extending this to larger sets of squares. Even if one considers the labels as distinct, it will be a challenge to list those identifications that do not induce additional four-cycles. Further, even with software to figure out isomorphism types, I think the number of such types will be exponential in the number of squares, if not doubly exponential, as it seems to me to be enumerating certain 4-designs.

$\endgroup$
1
$\begingroup$

Here is one more construction which covers a lot of graphs: start with a $4$-regular graph with girth at least $5$, take the line graph and delete a perfect matching in each resulting $K_4$...

This may get us almost all answers to the second question: If we start with an answer to the second question, and "fill in" all squares to make $C_4$s, we end up with a line graph of a $4$-regular graph. Not necessarily girth greater $3$, though.

To get all such graphs this way, you need to start with any $4$-regular graph, take the line graph, and then carefully delete the matchings to avoid extra squares. Describing what "carefully" entails, and deciding if it is even possible, may turn out to be difficult, though.

$\endgroup$
3
  • $\begingroup$ Ah, I was just typing this exact same thing in when the "new answer" notification arrived $\endgroup$ Nov 20, 2014 at 5:02
  • $\begingroup$ Also, you mean that you fill the squares to make $K_4$s (just a typo) $\endgroup$ Nov 20, 2014 at 5:03
  • $\begingroup$ This is the same as the medial graph construction in my answer. $\endgroup$ Nov 20, 2014 at 5:33
0
$\begingroup$

As a matter of fact, I have encountered this family of 4-regular graphs, where every edges lies in exactly one C4, and no two C4 share more than one vertex. You obtain any such graph with the following operation: - begin with any 3-regular graph G of girth at least 5, together with a perfect matching M. - Construct the graph H whose vertices are E(G)\M, and connect the pairs which cover a given edge of the matching M (so at distance exactly 2, linked by an edge of M). The graph H has the desired property, and you can reach any graph with this property with a well chosen G and M.

I now have a further question: What is the maximum possible (fractional) chromatic number of the square of such a graph? Could it be at most 8, possibly when the incidence graph of the C4's has sufficiently large girth?

$\endgroup$
1
  • 1
    $\begingroup$ It will be better to ask your question separately. $\endgroup$ Dec 21, 2017 at 10:10

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.