Graphs with at most two moplexes Dallard, Clément; Ganian, Robert; Hatzel, Meike ...
Journal of graph theory,
05/2024
Journal Article
Peer reviewed
Abstract A moplex is a natural graph structure that arises when lifting Dirac's classical theorem from chordal graphs to general graphs. The notion is known to be closely related to lexicographic ...searches in graphs as well as to asteroidal triples, and has been applied in several algorithms related to graph classes, such as interval graphs, claw‐free, and diamond‐free graphs. However, while every noncomplete graph has at least two moplexes, little is known about structural properties of graphs with a bounded number of moplexes. The study of these graphs is, in part, motivated by the parallel between moplexes in general graphs and simplicial modules in chordal graphs: unlike in the moplex setting, properties of chordal graphs with a bounded number of simplicial modules are well understood. For instance, chordal graphs having at most two simplicial modules are intervals. In this work, we initiate an investigation of ‐moplex graphs, which are defined as graphs containing at most moplexes. Of particular interest is the smallest nontrivial case , which forms a counterpart to the class of interval graphs. As our main structural result, we show that, when restricted to connected graphs, the class of 2‐moplex graphs is sandwiched between the classes of proper interval graphs and cocomparability graphs; moreover, both inclusions are tight for hereditary classes. From a complexity‐theoretic viewpoint, this leads to the natural question of whether the presence of at most two moplexes guarantees a sufficient amount of structure to efficiently solve problems that are known to be intractable on cocomparability graphs, but not on proper interval graphs. We develop new reductions that answer this question negatively for two prominent problems fitting this profile, namely, Graph Isomorphism and Max‐Cut. On the other hand, we prove that every connected 2‐moplex graph contains a Hamiltonian path, generalising the same property of connected proper interval graphs. Furthermore, for graphs with a higher number of moplexes, we lift the previously known result that graphs without asteroidal triples have at most two moplexes to the more general setting of larger asteroidal sets.
Full text
Available for:
BFBNIB, FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SBCE, SBMB, UL, UM, UPUK
Moplexes are natural graph structures that arise when lifting Dirac’s classical theorem from chordal graphs to general graphs. The notion is known to be closely related to lexicographic searches in ...graphs as well as to asteroidal triples, and has been applied in several algorithms related to graph classes such as interval graphs, claw-free, and diamond-free graphs. However, while every non-complete graph has at least two moplexes, little is known about structural properties of graphs with a bounded number of moplexes. The study of these graphs is, among others, motivated by the parallel between moplexes in general graphs and simplicial modules in chordal graphs: unlike in the moplex setting, properties of chordal graphs with a bounded number of simplicial modules are well understood. For instance, chordal graphs having at most two simplicial modules are interval.
In this work we initiate an investigation of k-moplex graphs, which are defined as graphs containing at most k moplexes. Of particular interest is the smallest nontrivial case, k = 2, which forms a counterpart to the class of interval graphs. As our main structural result, we show that the class of connected 2-moplex graphs is sandwiched between the classes of proper interval graphs and cocomparability graphs; moreover, both inclusions are tight for hereditary classes. From a complexity theoretic viewpoint, this leads to the natural question of whether the presence of at most two moplexes guarantees a sufficient amount of structure to efficiently solve problems that are known to be intractable on cocomparability graphs, but not on proper interval graphs. We develop new reductions that answer this question negatively for two prominent problems fitting this profile, namely Graph Isomorphism and Max-Cut. Furthermore, for graphs with a higher number of moplexes, we lift the previously known result that graphs without asteroidal triples have at most two moplexes to the more general setting of larger asteroidal sets. We also discuss sufficient conditions for the existence of Hamiltonian paths in 2-moplex graphs as well as connections with avoidable vertices.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Circle graphs are intersection graphs of chords in a circle and k-polygon graphs are intersection graphs of chords in a convex k-sided polygon where each chord has its endpoints on distinct sides. ...The k-polygon graphs, for k≥2, form an infinite chain of graph classes, each of which contains the class of permutation graphs. The union of all of those graph classes is the class of circle graphs. The polygon number ψ(G) of a circle graph G is the minimum k such that G is a k-polygon graph. Given a circle graph G and an integer k, determining whether ψ(G)≤k is NP-complete, while the problem is solvable in polynomial time for fixed k.
In this paper, we show that ψ(G) is always at least as large as the asteroidal number of G, and equal to the asteroidal number of G when G is a connected distance hereditary graph that is not a clique. This implies that the classes of distance hereditary permutation graphs and distance hereditary AT-free graphs are the same, and we give a forbidden subgraph characterization of that class. We also establish the following upper bounds: ψ(G) is at most the clique cover number of G if G is not a clique, at most 1 plus the independence number of G, and at most ⌈n∕2⌉ where n≥3 is the number of vertices of G. Our results lead to linear time algorithms for finding the minimum number of corners that must be added to a given circle representation to produce a polygon representation, and for finding the asteroidal number of a distance hereditary graph, both of which are improvements over previous algorithms for those problems.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Asteroidal Triple‐free (AT‐free) graphs have received considerable attention due to their inclusion of various important graphs families, such as interval and cocomparability graphs. The asteroidal ...number of a graph is the size of a largest subset of vertices such that the removal of the closed neighborhood of any vertex in the set leaves the remaining vertices of the set in the same connected component. (AT‐free graphs have asteroidal number at most 2.) In this article, we characterize graphs of bounded asteroidal number by means of a vertex elimination ordering, thereby solving a long‐standing open question in algorithmic graph theory. Similar characterizations are known for chordal, interval, and cocomparability graphs.
Full text
Available for:
BFBNIB, FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SBCE, SBMB, UL, UM, UPUK
We analyze the relation between three parameters of a chordal graph G: the number of non-separating cliques nsc(G), the asteroidal number an(G) and the leafage l(G). We show that an(G) is equal to ...the maximum value of nsc(H) over all connected induced subgraphs H of G. As a corollary, we prove that if G has no separating simplicial cliques then an(G)=l(G).
A graph G is minimal k-asteroidal if an(G)=k and an(H)<k for every proper connected induced subgraph H of G. The family of minimal k-asteroidal chordal graphs is unknown for every k>3; for k=3 it is the family described by Lekerkerker and Boland to characterize interval graphs. We prove that, for every minimal k-asteroidal chordal graph, all the above parameters are equal to k. In addition, we characterize the split graphs that are minimal k-asteroidal and obtain all the minimal 4-asteroidal split graphs. Finally, we applied our results on asteroidal sets to describe the clutters with k edges that are minor-minimal in the sense that every minor has less than k edges.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Let
G be a connected chordal graph. The relation between the number of non-separating cliques of
G, denoted by
nsc
(
G
)
, and the size of a largest asteroidal set of
G, denoted by
an
(
G
)
, is ...studied. We show that
an
(
G
)
is equal to the maximum
nsc
(
H
)
taken over all induced connected subgraphs
H of
G. As a result, we provide a subclass of chordal graphs whose asteroidal number equals the leafage. We prove that the given class contains all the minimal
k-asteroidal chordal graphs. Finally, we present the family of minimal 4-asteroidal split graphs.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK, ZRSKP
We introduce a natural heuristic for approximating the treewidth of graphs. We prove that this heuristic gives a constant factor approximation for the treewidth of graphs with bounded asteroidal ...number. Using a different technique, we give a
O(
log
k)
approximation algorithm for the treewidth of arbitrary graphs, where
k is the treewidth of the input graph.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
PDF
