Regular graphs with large Italian domatic number: Sage Code

All code was run in a jupyter notebook with Sage 8.7. The notebook is located here: ItalianDomatic.ipynb. This can be run online without downloading Sage by accessing it on myBinder at https://mybinder.org/v2/gh/sjlyle/ItalianDomatic/main and clicking on ItalianDomatic.ipynb. Alternatively, you can load each cell separately below (or execute in mybinder). There are four cells/parts, and the action of each part is described below.

1. Part 1: ItalianDomatic_Part1.ipynb
   There are 23 cubic triangle-free graphs on 10 vertices (22 connected, and one disconnected). Graph6 code for the 22 connected graphs can be found at House of Graphs (girth >= 4) , and the only disconnected graph is the graph formed by the disjoint union of two copies of the unique cubic, triangle-free graph on 6 vertices. This same list can also be generated in Sage using Nauty (however, the graph6 codes differ as the graph6 is not unique up to isomorphism; the outputs below suppose the list from the House of Graphs).This section of the code reads in the 23 graphs, and then screens those that can be eliminated from consideration by use of Lemma 2 or Lemma 3 from the paper.
   
   The result of running this code should be to identify seven possible candidate graphs G that could have a pefect 2-factor in G-e for every edge e (these are indexed by their location in the list).
   Output
   The Remaining Candidates:
   Graph 0 : KCHY@eAGKOGB
   Graph 4 : KCHY@eAWCO?F
   Graph 6 : KC`Y@aAWHO?X
   Graph 10 : KKhY?aAGOE?F
   Graph 17 : KhhK?GQ?oa?F
   Graph 20 : KMo@_K`@KG@B
   Graph 22 : K??FFB_F?wB_
   
   
   
2. Part 2: ItalianDomatic_Part2.ipynb
   Once the list has been winnowed down to those graphs which may have a two-factor in G - e, for every edge e, the next step is to check if they satisfy the SPER-property. This is done as follows:
   1. First, load the possible types of perfect 2-factors. In a triangle-free graph on 10 vertices, this can only be either a ten-cycle, a vertex-disjoint four cycle and six cycle, or two vertex disjoint five cycles.
   2. There may be more than one perfect 2-factor in G - e, so we choose a few initial edges to start with so that specifying the perfect 2-factor in G - e for these edges is enough to uniquely determine the remaining 2-factors (if possible). Check if each type of factor is a subgraph of G - e (for each edge), and save these in a list.
   3. Next, we check the entire graph. Iterate through the permutations of the perfect 2-factors found in the previous step. We create an adjacency matrix (AM) for a potential "host graph", where the vertices for AM are the edges in the original graph G, and edges e and e' are adjacent if the edge e is in the perfect 2-factor for G - e' (and vice versa). As a new edge e is "checked" (finding perfect 2-factors M_e in G - e), the SPER property is checked (i.e., if e is in M_e', then e' is in M_e) against the partial information in the adjacency matrix. If no problems, we add it to a list of perfect 2-factors for e.
   Lastly, if no perfect 2-factors exist for an edge e, the graph does not satisfy the SPER property with the initial 2-factors used. If multiple 2-factors exist, move on to another edge. If exactly one 2-factor exists, update the adjacency matrix with the information.
   4. The number of initial edges chosen is 3, and in this case, for each graph, this is enough to ensure that at the end, either the SPER property is not satisfied, or every 2-factor is uniquely idenitified, and the corresponding host graph is output.
   
   The result of running this code should be the Graph6 code for any potential host graph. Note: the graph G should be manually set to each of the graphs Gr1 through Gr7 (on the line 9 of the actual code) to check each case.
   Output For G = Gr1
   Graph 1 : Intersect. graph KCHY@eAGKOGB yields QEYbtZSZrtTlt[tkult]i]ujYlO
   
   Output For G = Gr2
   Graph 1 : Intersect. graph KCHY@eAWCO?F yields QEYblZWZrtTlu[tkuxdZm]ujUl_
   
   Output For G = Gr3
   In this case, no initial perfect 2-factors on the give rise to a host graph (Gr3 does not satisfy the SPER property).
   
   Output For G = Gr4
   In this case, no initial perfect 2-factors on the give rise to a host graph (Gr4 does not satisfy the SPER property).
   
   Output For G = Gr5
   In this case, no initial perfect 2-factors on the give rise to a host graph (Gr5 does not satisfy the SPER property).
   
   Output For G = Gr6
   Graph 1 : Intersect. graph KMo@_K`@KG@B yields QEYdZXtmb^UmucuTuuusuZyjTlO
   
   Output For G = Gr7
   ----------------------------
   Graph 1 : Intersect. graph K??FFB_F?wB_ yields QBjB\jWjrtYktZjtNVBtZt\inZ?
   Graph 2 : Intersect. graph K??FFB_F?wB_ yields QBjB\jWmZmXsrjm\MzBmZrlixz?
   Graph 3 : Intersect. graph K??FFB_F?wB_ yields QBjB\jWtZtTwjrt\NVBtZjtjTz?
   Graph 4 : Intersect. graph K??FFB_F?wB_ yields QBjB\jWrjmVKmZrlMzBmZm\jMz?
   Graph 5 : Intersect. graph K??FFB_F?wB_ yields QBjB\jWjujNStZ]lTzBtZjtjTz?
   Graph 6 : Intersect. graph K??FFB_F?wB_ yields QBjB\jWm]\Mwrj\tVNBmZm\jMz?
   Graph 7 : Intersect. graph K??FFB_F?wB_ yields QBjB\jWt\]NSjr]lYnBtZt\inZ?
   Graph 8 : Intersect. graph K??FFB_F?wB_ yields QBjB\jWrlrMwmZ\tXvBmZrlixz?
   Graph 9 : Intersect. graph K??FFB_F?wB_ yields QBjB\jWmZmXs\rrlVNE\Zm\hvZ?
   Graph 10 : Intersect. graph K??FFB_F?wB_ yields QBjB\jWjrtYk]jt\TzEjZjthyz?
   Graph 11 : Intersect. graph K??FFB_F?wB_ yields QBjB\jWtZtTw]jjtYnD]Zt\hyz?
   Graph 12 : Intersect. graph K??FFB_F?wB_ yields QBjB\jWrjmVK\rm\XvDrZrlhvZ?
   Graph 13 : Intersect. graph K??FFB_F?wB_ yields QBjB\jWm]\Mw\rm\XvE\Z\tixz?
   Graph 14 : Intersect. graph K??FFB_F?wB_ yields QBjB\jWjujNS]jjtYnEjZ]linZ?
   Graph 15 : Intersect. graph K??FFB_F?wB_ yields QBjB\jWt\]NS]jt\TzD]Z]ljTz?
   Graph 16 : Intersect. graph K??FFB_F?wB_ yields QBjB\jWrlrMw\rrlVNDrZ\tjMz?
   Graph 17 : Intersect. graph K??FFB_F?wB_ yields QBjB\jW\trXsmZrlMzE\Z\tixz?
   Graph 18 : Intersect. graph K??FFB_F?wB_ yields QBjB\jW]l]Ykjrt\NVEjZ]linZ?
   Graph 19 : Intersect. graph K??FFB_F?wB_ yields QBjB\jW\u\VKrjm\MzDrZ\tjMz?
   Graph 20 : Intersect. graph K??FFB_F?wB_ yields QBjB\jW]mjTwtZjtNVD]Z]ljTz?
   Graph 21 : Intersect. graph K??FFB_F?wB_ yields QBjB\jW\u\VKmZ\tXvE\Zm\hvZ?
   Graph 22 : Intersect. graph K??FFB_F?wB_ yields QBjB\jW]mjTwjr]lYnEjZjthyz?
   Graph 23 : Intersect. graph K??FFB_F?wB_ yields QBjB\jW\trXsrj\tVNDrZrlhvZ?
   Graph 24 : Intersect. graph K??FFB_F?wB_ yields QBjB\jW]l]YktZ]lTzD]Zt\hyz?
   
   
   
3. Part 3: ItalianDomatic_Part3.ipynb
   For one graph in particular, there are many corresponding host graphs, but it turns out that they are isomorphic. This part simply loads the output from Part 2 to identify only non-isomorphic candidates.
   
   The result of running this code should be a list of the non-isomorphic host graphs generated in the previous part.
   Output
   Non-isomorphic Candidates:
   Graph 0 : QEYbtZSZrtTlt[tkult]i]ujYlO
   Graph 1 : QEYblZWZrtTlu[tkuxdZm]ujUl_
   Graph 2 : QEYdZXtmb^UmucuTuuusuZyjTlO
   Graph 3 : QBjB\jWjrtYktZjtNVBtZt\inZ?
   
   
4. Part 4: ItalianDomatic_Part4.ipynb
   In this case, we look at the complement of G, i.e. G, to see if G has an Italian domatic number of δ(G ) + 2, that is, d_I(G) = δ(G ) + 2. This is the only way to satisfy the Nordhaus-Gaddum equation d_I(G) + d_I(G) = n +2, where n is the number of vertices of G. Since the complement must also satisfy Lemma 1, this is done by simply checking for independent sets of the correct size in G. This is checked by accomplishing the following steps:
   1. First, check the graph G. This is really unnecessary; G is a host graph for an intersection graph that satisfies the SPER-2 propery, but the same process will be used for the complement.
      1. First, determine the size and number of independent sets needed to satisfy Lemma 1 for the graph G, given the number of vertices and minimum degree of the graph (since this is only run for 10-regular graphs on 18 vertices, there should be 12 sets, each consisting of 3 vertices.
      2. Iterate through the maximal indepedent sets. Make a list R of those with the correct number of vertices. Then, for a specific independent set S, check all vertices not in S. Each should be adjacent to exactly two vertices in S (Condition 3 of Lemma 1: since these independent sets are maximal, no vertex not in S should be adjacent to zero vertices of S). There should be at least 12 sets that satisfy this property (Condition 4 of Lemma 1 would still need to be checked).
   2. Next, check the complement, G.
      1. First, determine the size and number of independent sets needed to satisfy Lemma 1 for the graph G, given the number of vertices and minimum degree of the graph. The complement will be 7-regular on 18 veritices, so there should be 9 sets, each consisting of 4 vertices.
      2. Iterate through the indepedent sets. Make a list R of those with the correct number of vertices. Then, for a specific independent set x, check all vertices not in S. Each should be adjacent to exactly two vertices in x (Condition 3 of Lemma 1). In all cases, there end up being 0 sets that satisfy this property.
   
   
   The result of running this code should be output indicating if it is possible for d_I(G) = δ(G ) + 2 for any host graph G found in the previous parts.
   Output
   Host graph 0 with graph6 code QEYbtZSZrtTlt[tkult]i]ujYlO
   For the original graph with graph6 code QEYbtZSZrtTlt[tkult]i]ujYlO
   Set Size (calculated): 3
   Number of Sets needed (calculated): 12
   Number of independent sets of correct length in G: 15
   Number of Italian dominating sets of correct size: 15
   For the complement graph with graph6 code Qxd[IcjcKIiQIbIRHQI`T`HSdQg
   Set Size (calculated) - complement: 4
   Number of Sets needed (calculated) - complement: 9
   Number of independent sets of correct size: 27
   Number of Italian dominating sets of correct size: 0
   ------------------
   Host graph 1 with graph6 code QEYblZWZrtTlu[tkuxdZm]ujUl_
   For the original graph with graph6 code QEYblZWZrtTlu[tkuxdZm]ujUl_
   Set Size (calculated): 3
   Number of Sets needed (calculated): 12
   Number of independent sets of correct length in G: 16
   Number of Italian dominating sets of correct size: 16
   For the complement graph with graph6 code Qxd[QcfcKIiQHbIRHEYcP`HShQW
   Set Size (calculated) - complement: 4
   Number of Sets needed (calculated) - complement: 9
   Number of independent sets of correct size: 30
   Number of Italian dominating sets of correct size: 0
   ------------------
   Host graph 2 with graph6 code QEYdZXtmb^UmucuTuuusuZyjTlO
   For the original graph with graph6 code QEYdZXtmb^UmucuTuuusuZyjTlO
   Set Size (calculated): 3
   Number of Sets needed (calculated): 12
   Number of independent sets of correct length in G: 14
   Number of Italian dominating sets of correct size: 14
   For the complement graph with graph6 code QxdYceIP[_hPHZHiHHHJHcDSiQg
   Set Size (calculated) - complement: 4
   Number of Sets needed (calculated) - complement: 9
   Number of independent sets of correct size: 18
   Number of Italian dominating sets of correct size: 0
   ------------------
   Host graph 3 with graph6 code QBjB\jWjrtYktZjtNVBtZt\inZ?
   For the original graph with graph6 code QBjB\jWjrtYktZjtNVBtZt\inZ?
   Set Size (calculated): 3
   Number of Sets needed (calculated): 12
   Number of independent sets of correct length in G: 12
   Number of Italian dominating sets of correct size: 12
   For the complement graph with graph6 code Q{S{aSfSKIdRIcSIog{IcIaTOcw
   Set Size (calculated) - complement: 4
   Number of Sets needed (calculated) - complement: 9
   Number of independent sets of correct size: 0
   Number of Italian dominating sets of correct size: 0