Advanced Search

Question: The labeling problem of elimination sequences in chordal graph testing.

Question:The labeling problem of elimination sequences in chordal graph testing.

lcz 959 Maple 2023
graphtheory
June 08 2023
1

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.

> 

with(GraphTheory):
g1:=PathGraph(10):
g2:=CycleGraph(3):
> 

s:=LexicographicProduct(g1,g2):
> 

IsChordal(s,eliminationordering=true)

true, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]

 (1)
> 

DrawGraph(s)

 
> 

Vertices(s)

["1:1", "1:2", "1:3", "2:1", "2:2", "2:3", "3:1", "3:2", "3:3", "4:1", "4:2", "4:3", "5:1", "5:2", "5:3", "6:1", "6:2", "6:3", "7:1", "7:2", "7:3", "8:1", "8:2", "8:3", "9:1", "9:2", "9:3", "10:1", "10:2", "10:3"]

 (2)

Download ischordgraph.mw
Please Wait...