6
$\begingroup$

An undirected graph $G$ is chordal if it has no induced cycles of length 4 or more. A set $S \subseteq V(G)$ disconnects a vertex $a$ from vertex $b$ if every path of $G$ between $a$ and $b$ contains a vertex from $S$. A non-empty set $S \subseteq V(G)$ is a minimal separator of $G$ if there exists $a$ and $b$ such that (i) $S$ disconnects $a$ from $b$ in $G$, and (ii) no proper subset of $S$ disconnects $a$ from $b$ in $G$.

A $k$-tree is a chordal graph where all maximal cliques are of size $k+1$ and all minimal separators of size $k$. A block graph is a chordal graph, where maximal cliques can be of any size, but the minimal separators are of size one. What about chordal graphs where the maximal cliques can be of any size, but there's a constraint on the size of the minimal separators? This feels like a rather natural variant, but I was unable to find a reference that captures this.

Let $k$ be a positive integer. Consider a chordal graph such that the size of every minimal separator $|S| = k$. (Alternatively, replace $=$ with $\leq$). Have such graphs been studied before somewhere?

For $k=1$, such a graph is known as a block graph. What about $k \geq 2$?

$\endgroup$
9
$\begingroup$

In this paper graphs in which the size of every minimal separator $|S| \le k$ are called graphs of separability at most $k$.

Theorem 1 of that paper implies that chordal graphs of separability at most $2$ are obtained from complete graphs by "gluing" along a vertex or an edge.

$\endgroup$
  • 6
    $\begingroup$ There is a related paper that could be interesting in this context. $\endgroup$ – user13136 May 17 '13 at 16:24
4
$\begingroup$

Kumar, P. S., & Madhavan, C. E. (1998). Minimal vertex separators of chordal graphs. Discrete Applied Mathematics, 89(1), 155-168 define chordal graphs where every minimal separator is of size exactly $k$ as $k$-separator-chordal graphs. They generalize $k$-trees.

In a later paper, Kumar, P. S., & Madhavan, C. E. (2002). Clique tree generalization and new subclasses of chordal graphs. Discrete Applied Mathematics, 117(1), 109-131 the same authors discuss $k$-separator-chordal graphs more in a slightly different context. See Section 6.2 in the paper.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.