New Conjectures

[thenealon]

read to bottom of thread to find still-open conjectures UNDECIDED (tested for all of graph_objects):

(((is_line_graph)&(is_complement_of_chordal))&(has_radius_equal_diameter))->(is_hamiltonian)

UNDECIDED (tested for graph_objects w n<40):

(((is_locally_bipartite)->(is_line_graph))&(is_strongly_regular))->(is_hamiltonian)
(((is_independence_irreducible)->(is_line_graph))&(is_strongly_regular))->(is_hamiltonian)
(((is_factor_critical)&(has_radius_equal_diameter))&((is_perfect)^(has_lovasz_theta_equals_alpha)))->(is_hamiltonian)  
(((is_factor_critical)^(is_independence_irreducible))&((is_H_free)&(has_radius_equal_diameter)))->(is_hamiltonian)
((alpha_leq_order_over_two)&(is_locally_two_connected))->(is_hamiltonian)
((~(is_perfect))&(girth_greater_than_2log))->(is_hamiltonian)
(((is_perfect)&(is_three_connected))&(alpha_leq_order_over_two))->(is_hamiltonian)
(((is_quasi_regular)&(is_H_free))&(has_dart))->(is_hamiltonian)
(((diameter_equals_radius)&(is_line_graph))&(~(is_quasi_regular)))->(is_hamiltonian)
((~(is_c4_free))&(is_locally_connected))->(is_hamiltonian)
((is_quasi_regular)&(is_cartesian_product))->(is_hamiltonian)
(((has_radius_equal_diameter)&(has_kite))&(is_quasi_regular))->(is_hamiltonian)
(((has_radius_equal_diameter)&(is_line_graph))&(~(is_perfect)))->(is_hamiltonian)
(((has_radius_equal_diameter)&(is_line_graph))&(~(is_quasi_regular)))->(is_hamiltonian)
((~((is_quasi_regular)|(is_perfect)))&(has_radius_equal_diameter))->(is_hamiltonian)

[a234]

CE to ((is_quasi_regular)&(is_cartesian_product))->(is_hamiltonian):

q=Graph('K{CY?CBG??_B').cartesian_product(k2)
is_quasi_regular(q)
True
q.is_hamiltonian()
False

[a234]

CE to ((has_radius_equal_diameter)&(is_line_graph)&(~(is_perfect)))->(is_hamiltonian) and ((has_radius_equal_diameter)&(is_line_graph)&(~(is_quasi_regular)))->(is_hamiltonian): (Credits: https://www.math.wvu.edu/~hjlai/ClawFreeGraphs-10-20-2012.pdf)

q=graphs.PetersenGraph();
for p in [0..9]:
    q.add_vertex(p+10)
    q.add_edge(p,p+10)
g=q.line_graph()

is_quasi_regular(g)
False

g.is_perfect()
False

g.diameter()==g.radius()
True

g.is_hamiltonian()
False

[a234]

It seems that there is a bug in the program: diameter_equals_radius and has_radius_equal_diameter are essentially the same thing.

[thenealon]

This is two; the one of these is redundant. It doesn't hurt anything for the moment, but may be confusing later.

[a234]

CE to ((~(is_perfect))&(girth_greater_than_2log))->(is_hamiltonian)

g=glasses_graph(17,17);
((~(g.is_perfect())) and (girth_greater_than_2log(g)))
True
g.is_hamiltonian()
False

[a234]

CE to (((is_factor_critical)&(has_radius_equal_diameter))&((is_perfect)^(has_lovasz_theta_equals_alpha)))->(is_hamiltonian)

g=Graph('N_goPePG?_POB_aWyB_')
is_factor_critical(g)&has_radius_equal_diameter(g)&has_lovasz_theta_equals_alpha(g)
True
g.is_hamiltonian()
False

[a234]

CE to (((is_factor_critical)^(is_independence_irreducible))&((is_H_free)&(has_radius_equal_diameter)))->(is_hamiltonian)

g=Graph('LU@CIW_O?O_CAB')
is_factor_critical(g)&has_radius_equal_diameter(g)&is_H_free(g)
True
g.is_hamiltonian()
False

[a234]

CE to (((is_quasi_regular)&(is_H_free))&(has_dart))->(is_hamiltonian)

g=Graph('Iv??G[N]?')
(is_quasi_regular(g))&(is_H_free(g))&(has_dart(g))
True
g.is_hamiltonian()
False

[thenealon]

CE to (((is_factor_critical)^(is_independence_irreducible))&((is_H_free)&(has_radius_equal_diameter)))->(is_hamiltonian)

This is not a counterexample; it is both factor critical and independence_irreducible so the first XOR clause fails.

[a234]

CE to (((has_radius_equal_diameter)&(has_kite))&(is_quasi_regular))->(is_hamiltonian):

g=Graph('Mt?GOGB@?CgHOKM??')
(is_quasi_regular(g))&(has_radius_equal_diameter(g))&(has_kite(g))
True
g.is_hamiltonian()
False

[a234]

CE to ((~((is_quasi_regular)|(is_perfect)))&(has_radius_equal_diameter))->(is_hamiltonian):

g=Graph('KGh?Q?ALCjQ[')
((~((is_quasi_regular(g))|(g.is_perfect())))&(has_radius_equal_diameter(g)))
1
g.is_hamiltonian()
False

[a234]

CE to ((~(is_c4_free))&(is_locally_connected))->(is_hamiltonian):

g=Graph('F?~vw')
((~(is_c4_free(g)))&(is_locally_connected(g)))
1
g.is_hamiltonian()
False

[a234]

The Triangle-Replaced Petersen is a CE to (((is_perfect)&(is_three_connected))&(alpha_leq_order_over_two))->(is_hamiltonian):

g=Graph(']t?G?C????_CAG@C?H?CG?G_?P??G_?P???G???W??G???P???K???BG???I???DF????b????')
(((g.is_perfect())&(is_three_connected(g)))&(alpha_leq_order_over_two(g)))
True
g.is_hamiltonian()
False

[a234]

The conjecture (((is_line_graph)&(is_complement_of_chordal))&(has_radius_equal_diameter))->(is_hamiltonian) is true: is_line_graph implies claw-free is_complement_of_chordal implies P6-free has_radius_equal_diameter implies 2-connected And every 2-connected (P6 ,claw )-free graph is hamiltonian (http://graphclasses.org/classes/refs1600.html#ref_1694). So the conjecture is true.

[a234]

This is not a counterexample; it is both factor critical and independence_irreducible so the first XOR clause fails.

Fixed:

g=Graph('J?CWcXAGn??')
(((is_factor_critical(g))^(is_independence_irreducible(g)))&((is_H_free(g))&(has_radius_equal_diameter(g))))
1
g.is_hamiltonian()
False

[a234]

CE to ((alpha_leq_order_over_two)&(is_locally_two_connected))->(is_hamiltonian):

g=Graph('K~e[Mm@oYaAg');
alpha_leq_order_over_two(g)&is_locally_two_connected(g)
True
g.is_hamiltonian()
False

[yirkajk]

This is not a counterexample; it is both factor critical and independence_irreducible so the first XOR clause fails. Fixed:

This graph is still both factor_critical and independence_irreducible. We found an unfortunate feature of sage that ^ is not XOR like it is in Python. Instead, ^ only performs exponentiation. To perform XOR, use ^^.

[yirkajk]

Remaining open conjectures from this issue:

# (((is_locally_bipartite)->(is_line_graph))&(is_strongly_regular))->(is_hamiltonian)
# (((is_independence_irreducible)->(is_line_graph))&(is_strongly_regular))->(is_hamiltonian)
# (((diameter_equals_radius)&(is_line_graph))&(~(is_quasi_regular)))->(is_hamiltonian)
# (((is_factor_critical)^(is_independence_irreducible))&((is_H_free)&(has_radius_equal_diameter)))->(is_hamiltonian)

Proof of # (((is_line_graph)&(is_complement_of_chordal))&(has_radius_equal_diameter))->(is_hamiltonian) still needs to be reviewed

[math1um]

We found an unfortunate feature of sage that ^ is not XOR like it is in Python. Instead, ^ only performs exponentiation.

"^" in the conjecture is a display (print) character. It represents a genuine XOR. The relevant check is done in the expressions.c code:

boolean handleCommutativeBinaryOperator_propertyBased(int id, boolean left, boolean right){
    if(left==UNDEFINED || right==UNDEFINED){
        return UNDEFINED;
    }
    if(id==0){
        return left && right;
    } else if(id==1){
        return left || right;
    } else if(id==2){
        return (!left) != (!right); //XOR
    } else {
        BAILOUT("Unknown commutative binary operator ID")
    }
}

void writeCommutativeBinaryOperatorExample_propertyBased(FILE *f){
    fprintf(f, "C 0    x & y\n");
    fprintf(f, "C 1    x | y\n");
    fprintf(f, "C 2    x ^ y (XOR)\n");
}

[a234]

# (((diameter_equals_radius)&(is_line_graph))&(~(is_quasi_regular)))->(is_hamiltonian) is the same as ((has_radius_equal_diameter)&(is_line_graph)&(~(is_quasi_regular)))->(is_hamiltonian), to which I have posted a counterexample.

[a234]

@thenealon is the Triangle-Replaced Petersen a CE to (((is_factor_critical)^(is_independence_irreducible))&((is_H_free)&(has_radius_equal_diameter)))->(is_hamiltonian)?

[thenealon]

Yes, this is a counterexample; "((false XOR true) AND true AND true) -> false" is (true AND true AND true) -> false, which is FALSE. Nice!

[thenealon]

It seems to me that the proof above for (((is_line_graph)&(is_complement_of_chordal))&(has_radius_equal_diameter))->(is_hamiltonian) is correct; however, the proper reference is probably

H.J. Broersma, H.J. Veldman, Restrictions on induced subgraphs ensuring Hamiltonicity or pancyclicity of K1,3-free graphs, Contemporary methods in graph theory, BI-Wiss.-Verl. 181-194 (199)

[a234]

It seems that the only SRGs which are line graphs are the line graphs of K_n and K_n,n, which are hamiltonian.

[yirkajk]

Remaining open conjectures:

# (((is_locally_bipartite)->(is_line_graph))&(is_strongly_regular))->(is_hamiltonian)
# (((is_independence_irreducible)->(is_line_graph))&(is_strongly_regular))->(is_hamiltonian)

Theorems (yay!): # (((is_line_graph)&(is_complement_of_chordal))&(has_radius_equal_diameter))->(is_hamiltonian)