5
$\begingroup$

Let $G$ be a simple connected graph that has at least one 1-factor. We'll define:
$G$ has property A iff it is edge-transitive.
$G$ has property B iff each edge belongs to the same number of 1-factors.

  • Is it obvious that $A\implies B$ ?
  • Is it possible to characterize the graphs that have B but not A?

I think that such graphs exist, but haven't been lucky yet. The "natural" candidates like a $C_{2k}$ along with its diagonals of a certain length don't seem to work but some come close to property B.

$\endgroup$
2
  • 2
    $\begingroup$ Yes it is obvious that A implies B... $\endgroup$ Jul 23, 2014 at 23:54
  • 1
    $\begingroup$ $A\Rightarrow B$ does not seem hard unless I'm missing something. Indeed, if $\varphi$ is an automorphism of $G$ and $f_1,f_2$ are different 1-factors sharing an edge $e$, then $\varphi(f_1)$ and $\varphi(f_2)$ are still different 1-factors sharing $\varphi(e)$. Therefore, there are equally many 1-factors passing through $e$ and $\varphi(e)$. $\endgroup$
    – user56203
    Jul 23, 2014 at 23:57

1 Answer 1

7
$\begingroup$

Here is an example for you to enjoy.

Take two disjoint copies of $K_{2,3}$, and form a cubic graph on 10 vertices by joining each of the three vertices of degree 2 in one copy to one of the vertices of degree 2 in the second copy. Here is Sage's picture of this graph.

Example graph

The graph is not edge-transitive because the three "cross edges" are not equivalent to the 12 other edges.

Each one-factor of this graph must use exactly one of the three cross-edges, e.g. 2-5, and a pair of opposite edges from each of the two four-cycles induced by the vertices on each side other than 2, and 5, making a total of four one-factors using 2-5.

Similarly there are four using 3-6 and four using 4-7. So we have twelve one-factors, giving a total of 60 edge-occurrences in a one-factor. Twelve of those occurrences were cross edges, leaving 48 occurrences shared between the remaining 12 edges, meaning that each non-cross-edge also appears in four one-factors.

$\endgroup$
2
  • $\begingroup$ As these graphs must supposedly have a relatively big automorphism group, do you think there is a chance of describing them all? $\endgroup$
    – Wolfgang
    Jul 24, 2014 at 9:07
  • $\begingroup$ @wolfgang I don't think there would be a hope of describing them all. At least that's what my general experience of graph theory says. $\endgroup$ Jul 24, 2014 at 12:54

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.