A chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. A perfect elimination ordering in a graph is an ordering of the vertices of the graph such that, for each vertex v, v and the neighbors of v that occur after v in the order form a clique.  A graph is chordal if and only if it has a perfect elimination ordering.

I  use IsChordal  to test whether the lexicographic product of  two graphs g1,g2 is a chordal graph. It returned true and provided a perfect elimination sequence 1, 2, ..., 30. However, vertices of s  are "1:1", "1:2", ..., "10:3", rather than using Arabic numerals. Therefore, it is difficult for me to extract useful information from the perfect elimination sequence.

Download ischordgraph.mw

Let's put aside the drawbacks of using goto for now. Below is the program I wrote. When I run it, it seems to execute, but the Maple interface displays the message "System error,,at top level". Does this trigger an internal warning in Maple?

for i to 4 do
    for j to 4 do
         print([i,j]):
        if i = 2 and j = 3 then
             goto(al):
        end if:
    end do:
end do:
al;

                             [1, 1]

                             [1, 2]

                             [1, 3]

                             [1, 4]

                             [2, 1]

                             [2, 2]

                             [2, 3]

                  System error, , at top level

                               al

• A set D of vertices in a graph G is a dominating set if each vertex of G that is not in D is adjacent to at least one vertex of D.
• The minimum cardinality among all dominating sets in G is called the domination number of G and denoted σ(G).
• We define the bondage number b(G) of a graph G to be the cardinality of a smallest set E of edges for which σ(G−E)>σ(G). 

In the previous post, Carl Love provided a code for calculating domination number, so we could use it to calculate bondage number. I wrote a piece of code using a relatively basic approach. I feel like there is room for improvement.  I still can't determine the bondage number of the following graph so far.

Bondage_number.mw

For arbitrarily given graph, it has been proved that determining its bondage number is NP-hard.

I always have a feeling that when removing subsets of edges, the symmetry of these edge subsets can be utilized. Above, we blindly traverse k-subsets of edges. If the graph is symmetric enough, perhaps we can reduce the amount of traversal. However, I have been struggling to understand how to express the symmetry of these edge subsets. Recently, I raised a similar question. 

• how-to-express-the-symmetry-of-two-subgraphs

In graph theory, a dominating set for a graph G is a subset D of its vertices, such that any vertex of G is either in D, or has a neighbor in D. The domination number γ(G) is the number of vertices in a smallest dominating set for G. The domination number is a well-known parameter in graph theory. But I am unable to find a built-in function in Maple to calculate the domination number of a graph. Did I miss something?

For example, I would like to calculate the domination number of the following graph.

ed:={{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 7}, {1, 9}, 
{1, 11}, {2, 3}, {2, 5}, {2, 6}, {2, 7}, {2, 12}, {2, 14},
 {3, 4}, {3, 7}, {3, 8}, {3, 9}, {3, 16}, {4, 5}, {4, 9}, 
{4, 10}, {4, 11}, {4, 17}, {5, 6}, {5, 11}, {5, 12}, {5, 19}, 
{6, 7}, {6, 12}, {6, 13}, {6, 14}, {6, 21}, {7, 8}, {7, 14}, 
{7, 15}, {8, 9}, {8, 14}, {8, 15}, {8, 16}, {8, 22}, {9, 10},
 {9, 16}, {9, 17}, {10, 11}, {10, 17}, {10, 18}, {10, 19}, 
{10, 23}, {11, 12}, {11, 18}, {11, 19}, {12, 13}, {12, 19}, 
{12, 20}, {13, 14}, {13, 19}, {13, 20}, {13, 21}, {13, 24}, 
{14, 15}, {14, 21}, {15, 16}, {15, 21}, {15, 22}, {15, 24}, 
{16, 17}, {16, 22}, {16, 23}, {17, 18}, {17, 22}, {17, 23}, 
{18, 19}, {18, 20}, {18, 23}, {18, 24}, {19, 20}, {20, 21}, 
{20, 23}, {20, 24}, {21, 22}, {21, 24}, {22, 23}, {22, 24}, {23, 24}};
g:=Graph(ed);

I find that no matter how I modify the style in the Maple command, the LaTeX output seems to be always fixed. This is a bit frustrating. 

G:=Graph(6,{{1,2},{1,4},{4,5},{2,5},{2,3},{3,6},{5,6}});
DrawGraph(G);
vp:=[[0,0],[0.5,0],[1,0],[0,0.5],[0.5,0.5],[1,0.5]]:
SetVertexPositions(G,vp):
DrawGraph(G);

Latex(G, terminal, 100, 100)

\documentclass{amsart}
\begin{document}
\begin{picture}(100,100)
\qbezier(12.40,87.60)(12.40,50.00)(12.40,12.40)
\qbezier(12.40,87.60)(31.20,50.00)(50.00,12.40)
\qbezier(12.40,12.40)(31.20,50.00)(50.00,87.60)
\qbezier(12.40,12.40)(50.00,50.00)(87.60,87.60)
\qbezier(50.00,87.60)(68.80,50.00)(87.60,12.40)
\qbezier(50.00,12.40)(68.80,50.00)(87.60,87.60)
\qbezier(87.60,87.60)(87.60,50.00)(87.60,12.40)
\put(12.400000,87.600000){\circle*{6}}
\put(10.194,96.943){\makebox(0,0){1}}
\put(12.400000,12.400000){\circle*{6}}
\put(8.726,3.531){\makebox(0,0){2}}
\put(50.000000,87.600000){\circle*{6}}
\put(50.000,97.200){\makebox(0,0){3}}
\put(50.000000,12.400000){\circle*{6}}
\put(50.000,2.800){\makebox(0,0){4}}
\put(87.600000,87.600000){\circle*{6}}
\put(91.274,96.469){\makebox(0,0){5}}
\put(87.600000,12.400000){\circle*{6}}
\put(89.806,3.057){\makebox(0,0){6}}
\end{picture}
\end{document}
 

DrawGraph(G,
stylesheet=[vertexborder=false,vertexpadding=20,edgecolor = "Blue",
vertexcolor="Gold",edgethickness=3], font=["Courier",10],size=[180,180])

Even when I change their colors (any other thing), they always go their own way. I don't know if there is a setting that can make the LaTeX output more flexible and in line with our expectations after adjustment.