11
$\begingroup$

All graphs discussed are finite and simple. The cycle sequence of a graph $G$, denoted $C(G)$, is the nondecreasing sequence of the lengths of all of the cycles in $G$, where cycles are distinguished by the vertices they contain, not by the edges they contain.

For example, $C(K_{3,2})=4,4,4$ and $C(K_4)=3,3,3,3,4$.

Two graphs are isoparic if they have the same number of vertices and the same number of edges.

Main question: If $G$ and $H$ are 2-connected nonisoparic graphs, can $C(G)=C(H)$?

The 2-connected condition is so we can't just make a bunch of edge-disjoint cycles that share a vertex. The nonisoparic condition is so we can ignore situations like the following:

isoparic graphs

These graphs are not isomorphic but are isoparic. Both graphs have the cycle sequence $3,3,4,5,5,6$ and can be viewed as just a square surrounded by two triangles. Perhaps there's a better way to ignore this trick besides the nonisoparic condition.

I'm interested more generally in finding out exactly what the cycle sequence can tell us. When is a cycle sequence realizable by a 2-connected graph? Is such a realization ever unique? I've looked at a couple dozen graphs on fewer than seven vertices and the only duplicate cycle sequences have been for the graphs shown above.

Thank you.

$\endgroup$
  • 1
    $\begingroup$ By "all of the cycles in $G$" do you mean all the simple cycles in $G$---no repetitions of vertices and edges allowed in a cycle? $\endgroup$ – Joseph O'Rourke Jan 24 '15 at 1:44
  • $\begingroup$ Yes, besides the repetition of the first and last vertex in the cycle of course. $\endgroup$ – jamisans Jan 24 '15 at 2:32
  • $\begingroup$ I believe you are asking, in other words, if two graphs have the same number of Hamiltonian induced subgraphs of order $n$ for each $n$, does it follow that they have (a) the same number of vertices and (b) the same number of edges? Have I got it right? $\endgroup$ – bof Jan 24 '15 at 3:41
  • $\begingroup$ Throwing in the 2-connected condition, that seems like an equivalent question to my main question. $\endgroup$ – jamisans Jan 24 '15 at 4:06
  • 1
    $\begingroup$ It seems that if you know this sequence and the adjacency matrix of the graph, then you can compute the matching polynomial, which is #P-complete. $\endgroup$ – Dima Pasechnik Jan 24 '15 at 13:23
10
$\begingroup$

Second Answer

I'm adding this as another separate answer, rather than editing the first "answer" because otherwise anyone coming late to this discussion will end up doubly confused.

So let's try again, and say that the answer to your question is still "Yes".

If you type the following into Sage

g1 = Graph("G?rFf_")
g2 = Graph("H??EDz{")

and then show them as before, we get

enter image description here enter image description here

then I think that they each have exactly 11 4-blobs and 4 6-blobs (using "blob" rather than overloading the word cycle) but one has 8 vertices and 12 edges and the other has 9 vertices and 13 edges.

Here's a list of the blobs for the first graph (preceded by the size)

4 5 4 1 0
4 6 4 1 0
4 6 5 1 0
4 7 4 1 0
4 7 5 1 0
4 7 6 1 0
4 7 6 2 0
4 7 6 2 1
4 7 6 3 0
4 7 6 3 1
4 7 6 3 2
6 7 6 4 2 1 0
6 7 6 4 3 1 0
6 7 6 5 2 1 0
6 7 6 5 3 1 0

and here's the ones for the second graph

4 8 6 1 0
4 8 7 2 0
4 8 7 3 0
4 8 7 3 2
4 8 7 4 0
4 8 7 4 2
4 8 7 4 3
4 8 7 5 0
4 8 7 5 2
4 8 7 5 3
4 8 7 5 4
6 8 7 6 2 1 0
6 8 7 6 3 1 0
6 8 7 6 4 1 0
6 8 7 6 5 1 0
$\endgroup$
  • $\begingroup$ If two $2$-connected graphs have the same number of blobs of every size, and if they have the same number of vertices (edges), must they have the same number of edges (vertices)? $\endgroup$ – bof Jan 24 '15 at 6:25
  • $\begingroup$ That's a good question. Was this the smallest pair of counterexamples? $\endgroup$ – jamisans Jan 24 '15 at 16:15
4
$\begingroup$

The answer to your question is "Yes". If you type the following into Sage

g1 = Graph("I?`D@bAfg")
g2 = Graph("I?AE@`g~o")

g1.show();
g2.show();

you get

enter image description here

enter image description here

which both have 5 triangles, 6 4-cycles, 5 5-cycles, 5 6-cycles, 4 7-cycles, 2 8-cycles and a single 9-cycle.

$\endgroup$
  • 1
    $\begingroup$ Nice illustration. However non-isoparic graphs are requested. I may have miscounted, but this pair seem isoparic to me. Gerhard "Or Maybe I'm Missing Something" Paseman, 2015.01.23 $\endgroup$ – Gerhard Paseman Jan 24 '15 at 1:54
  • 1
    $\begingroup$ First one has 15 edges, second one 16. $\endgroup$ – Gordon Royle Jan 24 '15 at 2:01
  • 1
    $\begingroup$ Thanks for taking the time to make these illustrations. I'm having a hard time seeing the six 4-cycles in the first graph though. I'm only getting $\{1,5,8,9\}, \{0,6,8,9\}, \{0,4,8,9\}, \{0,4,6,9\}$. $\endgroup$ – jamisans Jan 24 '15 at 2:28
  • $\begingroup$ @jamisans The program probably counted $\{ 0 ,6 , 8 ,9 \}$ as three different cycles: $$0-6-9-8-0 \\ 0-9-6-8-0 \\ 0-6-8-9-0$$ Your statement counts them as one. $\endgroup$ – Nick S Jan 24 '15 at 2:38
  • $\begingroup$ @NickS : The question says that "cycles are distinguished by the vertices they contain, not by the edges they contain." So it seems like jamisans does not want to count those three as distinct. $\endgroup$ – Dan Ramras Jan 24 '15 at 2:39

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.