Day7.sagews

#is the graph with g6 string "DqK" in gt.sage?

#to get a graph from a g6 string "DqK" use Graph("DqK")
my_graph = Graph("DqK")
my_graph.show()

load("gt-nb.sage")

loaded utilities loaded invariants loaded properties loaded theorems loaded graphs Remember to load DIMACS and Sloane graphs if you want them

load("gt-nb.sage")

loaded utilities loaded invariants loaded properties loaded theorems

#is my_graph already in gt.sage
len(graph_objects)

Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1043, in execute exec compile(block+'\n', '', 'single', flags=compile_flags) in namespace, locals File "", line 1, in <module> NameError: name 'graph_objects' is not defined

my_graph = Graph("DqK")

for g in graph_objects:
    if g.is_isomorphic(my_graph):
        print "my_graph is already there. woo-hoo!"
        break
       
#print "add my_graph to gt.sage. make this a githib issue!"

my_graph is already there. woo-hoo!

g = graph_objects[0]

g.show()

g.is_isomorphic(my_graph)

False

#we also want to investigate a conjecture systematically
#here's the conjecture: is_distance_regular)&(is_bipartite))->(is_hamiltonian)
#NOTE: a CE will be distance regular, bipartite and NOT hamiltonian
#search for graphs with these graphs: all graphs with some order, random graphs, graphs in gt.sage

#all graphs with order 4
#for sufficient condition conjectures, check that the graph is actually connected
for g in graphs(4,property = lambda g: g.is_connected()):
    if g.is_connected():
        if g.is_bipartite() and g.is_distance_regular() and not g.is_hamiltonian():
            print g.graph6_string()
            break
#if there's no output, there was no counterexample            

for g in graphs(8):
    if g.is_connected():
        if g.is_bipartite() and g.is_distance_regular() and not g.is_hamiltonian():
            print g.graph6_string()
            break

#check the conjecture for all graphs in gt.sage with no more than n vertices (50? what's too big?)
for g in graph_objects:
    if g.is_connected() and g.order() > 2 and g.order() <= 1000:
        if g.is_bipartite() and g.is_distance_regular() and not g.is_hamiltonian():
            print g.graph6_string()
            break

#now let's try neal's random graph generators
#note: we want distance-regular graphs SO neal says we should use the random regular graph generator
def rand_regular_connected(n,d):
    counter=0
    gnd = graphs.RandomRegular(d,n)
    while not gnd.is_connected():
        gnd = graphs.RandomRegular(d,n)
        counter=counter+1
        if counter==200:
            gnd=k3
    return gnd

graphs.RandomRegular

#lets generate and test 1000 random regular graphs with order 50 and regular of degree d=10
count = 0
for i in range(1000):    
    g = rand_regular_connected(50,10)
    #print g.order(), max(g.degree())
    if g.order() > 3:
        count += 1
        if g.is_bipartite() and g.is_distance_regular() and not g.is_hamiltonian():
            print g.graph6_string()
            break
print "checked {} graphs".format(count)            

checked 1000 graphs

k3 = graphs.CompleteGraph(3)
#[(is_clique)->(is_hamiltonian)] is TRUE
k3_4 = graphs.CompleteBipartiteGraph(3,4)
k5_5 = graphs.CompleteBipartiteGraph(5,5)
#(is_cycle)->(is_hamiltonian) is TRUE
k2 = graphs.CompleteGraph(2)
EH = graphs.EllinghamHorton54Graph()
#CLAIM: ((is_strongly_regular)&(is_bipartite))->(is_hamiltonian) is true for n>2
#NB presented a proof: we need to write this up!
pete = graphs.PetersenGraph()
c5 = graphs.CycleGraph(5)
fish = Graph([(0,1),(1,2),(2,3),(3,4),(4,5),(5,2),(2,0)])
c5_tail = graphs.CycleGraph(5)
#c5_tail.add_vertex()
c5_tail.add_edge(0,5)
bow_tie = Graph(5)
bow_tie.add_edges([(0,1),(1,2),(2,3),(3,4),(4,2),(2,0)])
c7 = graphs.CycleGraph(7)
c7_chord = graphs.CycleGraph(7)
c7_chord.add_edge(0,2)
glasses = Graph(7)
glasses.add_edges([(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,3),(3,0)])
p3 = graphs.PathGraph(3)
k5 = graphs.CompleteGraph(5)

triangle_with_tail = graphs.CompleteGraph(3)
triangle_with_tail.add_edge(0,3)
blanusa2 = graphs.BlanusaSecondSnarkGraph()
duplex = Graph("Iv?GOKFY?")
heawood = graphs.HeawoodGraph()
frucht = graphs.FruchtGraph()
nb1 = Graph("Edj_")
tutte = graphs.TutteGraph()
pete = graphs.PetersenGraph()

robertson = graphs.RobertsonGraph()
hoffman = graphs.HoffmanGraph()
folkman = graphs.FolkmanGraph()
house = graphs.HouseGraph()

subdivided_k5 = graphs.CompleteGraph(5)
subdivided_k5.subdivide_edge((0,1),1)
subdivided_k5.show()
subdivided_k5.chromatic_index()

grid_2_3=graphs.Grid2dGraph(2,3)
grid_3_3=graphs.Grid2dGraph(3,3)
grid_3_3_3 = graphs.GridGraph([3,3,3])
k_4_6 = graphs.CompleteBipartiteGraph(4,6)
k3_4_edge=graphs.CompleteBipartiteGraph(3,4)
k3_4_edge.add_edge(0,1)

current_graph_objects = [k3,pete,c5,k5_5,k3_4,EH,c7_chord,bow_tie,k5,p3,glasses,fish,c5_tail,triangle_with_tail]
current_graph_objects.append(blanusa2)
current_graph_objects.append(frucht)
current_graph_objects.append(heawood)
current_graph_objects.append(duplex)
current_graph_objects.append(nb1)
current_graph_objects.append(tutte)
current_graph_objects.append(hoffman)
current_graph_objects.append(robertson)
current_graph_objects.append(folkman)
current_graph_objects.append(house)
current_graph_objects.append(subdivided_k5)
current_graph_objects.append(gould)
current_graph_objects.append(grid_2_3)
current_graph_objects.append(grid_3_3_3)

5

#conjecture: if is_ore or is_overfull implies hamiltonian
for g in current_graph_objects:
    
    print g, is_ore(g), g.is_overfull(), g.is_hamiltonian()

Complete graph True True True Petersen graph False False False Cycle graph False True True Complete bipartite graph True False True Complete bipartite graph False False False Ellingham-Horton 54-graph False False False Cycle graph False False True Graph on 5 vertices False False False Complete graph True True True Path graph False False False Graph on 7 vertices False False False Graph on 6 vertices False False False Cycle graph False False False Complete graph False False False Blanusa Second Snark Graph False False False Frucht graph False False True Heawood graph False False True Graph on 10 vertices False False False Graph on 6 vertices False False False Tutte Graph False False False Hoffman Graph False False True Robertson Graph False True True Folkman Graph False False True House Graph False False True Complete graph True False True gould False False False 2D Grid Graph for [2, 3] False False True Grid Graph for [3, 3, 3] False False False

J~wWGGB?wF_

#want a CE to ((is_ore)|(is_overfull))->(is_hamiltonian)
#need a connected graph that is either ore or overfull and not hamltonian
#check the conjecture for all graphs in gt.sage with no more than n vertices (50? what's too big?)
for g in graph_objects:
    if g.is_connected() and g.order() > 2 and g.order() <= 1000:
        if (is_ore(g) or g.is_overfull()) and not g.is_hamiltonian():
            print g.graph6_string()
            g.show()
            break

J~wWGGB?wF_

g=Graph("J~wWGGB?wF_")
g.show()

is_ore(g)
g.is_overfull()
g.is_hamiltonian()

False True False

for gg in graph_objects:
    if gg.is_isomorphic(g):
        print gg.name()

throwing