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$
7
  • 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$ Jan 24, 2015 at 1:44
  • $\begingroup$ Yes, besides the repetition of the first and last vertex in the cycle of course. $\endgroup$
    – jamisans
    Jan 24, 2015 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, 2015 at 3:41
  • $\begingroup$ Throwing in the 2-connected condition, that seems like an equivalent question to my main question. $\endgroup$
    – jamisans
    Jan 24, 2015 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$ Jan 24, 2015 at 13:23

2 Answers 2

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$
2
  • $\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, 2015 at 6:25
  • $\begingroup$ That's a good question. Was this the smallest pair of counterexamples? $\endgroup$
    – jamisans
    Jan 24, 2015 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$
12
  • 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$ Jan 24, 2015 at 1:54
  • 1
    $\begingroup$ First one has 15 edges, second one 16. $\endgroup$ Jan 24, 2015 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, 2015 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, 2015 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, 2015 at 2:39

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.