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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Yes it is obvious that A implies B... $\endgroup$
    – Gordon Royle
    Commented 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
    Commented Jul 23, 2014 at 23:57

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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$
    – Gordon Royle
    Commented Jul 24, 2014 at 12:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .