14
$\begingroup$

Harary and Akiyama asked whether there exists a non self-complementary (SC) graph $G$ having the same chromatic polynomial as its complement.

It was later shown that there indeed exist such graphs and it was conjectured that all such graphs have the same degree sequence as their complement.

As it turns out this conjecture is false and for every $n \geq 9$ congruent to $0,1$ modulo 4 one can construct a graph having the same chromatic polynomial as its complement but different degree sequence.

Extending this problem, it is possible to show that for any $n \geq 8$ congruent to $0,1$ modulo 4 there exist a non SC graph having the same Tutte polynomial as its complement.

What I currently cannot solve is the following

Question 1. Is there a graph $G$ having different degree sequence from $\overline{G}$ but the same Tutte polynomial?

Question 2. Is there a non SC graph having the same Tutte polynomial as its complement and order congruent to $0$ modulo $4?$

What I basically tried was generating all non SC graphs with $n(n-1)/4$ edges and checked the respective Tutte polynomials. As it turns out such a graph has to have order $n \geq 12$ and there are way too many graphs to be checked by a standard computer in this manner. Hence I need a more clever approach for searching. A nice thing would be if I could quickly filter through the output of nauty, removing graphs with the same degree sequence as their complement. I am afraid Sage is too slow for that.

I recall someone on MO (G. Royle?) saying that the Tutte polynomial is not ''good'' at distinguishing degree related invariants hence I suspect that the answer to Question 1 is positive.

Edit. The paper solving the original question of Akiyama and Harary is this one. While the thing for the Tutte polynomial can be found in this preprint. I would like to point out that it is just a preprint hence it may contain errors.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ It might be useful to give explicit references for the known facts that you cite. $\endgroup$
    – Timothy Chow
    Commented Jun 4, 2013 at 20:28
  • 1
    $\begingroup$ In dx.doi.org/10.1006/jctb.2000.1988 Bollobás, Pebody and Riordan conjecture that for almost all random graphs the Tutte polynomial determines the graph up to isomorphism; they also show that there is no way to locally modify a graph to leave the Tutte polynomial unchanged while breaking isomorphism, other than removing loops and re-attaching them in different places. So even finding two non-isomorphic graphs with the same Tutte polynomial is likely to be hard; your questions seem to be even harder (unless the answers are negative). $\endgroup$
    – András Salamon
    Commented Jun 4, 2013 at 20:44
  • 2
    $\begingroup$ Comment part 1: Finding arbitrary pairs of graphs with the same Tutte polynomial is not too hard - Tutte gave a method for doing so, based on detaching a "piece" of the graph at a number of connection points, rotating it, and then reconnecting it. If you do this carefully, then you change isomorphism but not the Tutte polynomial. Tutte called these "rotors" and while they're not much used these days, a book by Godsil and someone had a section on it. $\endgroup$
    – Gordon Royle
    Commented Jun 5, 2013 at 1:40
  • 1
    $\begingroup$ Comment part 2: Finding 12-vertex graphs co-Tutte with their complements sounds like a fun computational project. I'd start by thinking about spanning trees - which graphs have the same number of spanning trees as their complement? [I don't have any more concrete suggestions about HOW to think about spanning trees at the moment, however] $\endgroup$
    – Gordon Royle
    Commented Jun 5, 2013 at 1:43
  • 3
    $\begingroup$ I can confirm that there are no examples on 12 vertices... I used geng to construct all the 12-vertex 33-edge graphs, keeping only those with the same number of triangles as their complement. Then computed spanning trees and kept only those with the same number as their complement. Then threw out those with symmetric degree sequence. Finally tested the handful of graphs that remained. $\endgroup$
    – Gordon Royle
    Commented Jun 7, 2013 at 1:54

1 Answer 1

Reset to default
5
$\begingroup$

If you allow $n=8$, the answer to question 1 2 is yes.

The graph on $8$ vertices with edges:

[(0, 3), (0, 5), (0, 6), (0, 7), (1, 4), (1, 6), (1, 7), (2, 4), (2, 6), (3, 5), (3, 7), (4, 5), (4, 7), (6, 7)]

is a solution.

Found $8$ solutions for $n=8$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Aaah, I am so glad I asked this. Somehow I often overlook such things. Anyhow more precisely I was looking for a graph of order $4k$ that has the same subgraph description (as defined in the preprint) as its complement but it appears we have such graphs on 8 vertices as well. Thanks for bringing this up. $\endgroup$
    – Jernej
    Commented Jun 5, 2013 at 10:30

You must log in to answer this question.

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