<p><a href="http://www.sciencedirect.com/science/article/pii/S0166218X98001231" rel="nofollow">Kumar, P. S., &amp; Madhavan, C. E. (1998). Minimal vertex separators of chordal graphs. Discrete Applied Mathematics, 89(1), 155-168</a> define chordal graphs where every minimal separator is of size exactly $k$ as <em>$k$-separator-chordal graphs</em>. They generalize $k$-trees.</p>

<p>In a later paper, <a href="http://www.sciencedirect.com/science/article/pii/S0166218X0000336X" rel="nofollow">Kumar, P. S., &amp; Madhavan, C. E. (2002). Clique tree generalization and new subclasses of chordal graphs. Discrete Applied Mathematics, 117(1), 109-131</a> the same authors discuss $k$-separator-chordal graphs more in a slightly different context. See Section 6.2 in the paper.</p>

CC BY-SA 3.0
2013-05-31T03:59:05.590Z
2013-05-31T22:25:33.580Z
2013-05-31T22:25:33.580Z
Juho
<p>In <a href="http://www.sciencedirect.com/science/article/pii/S0166218X11000424">this paper</a> graphs in which the size of every minimal separator $|S| \le k$ are called <em>graphs of separability at most $k$</em>.</p>

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

CC BY-SA 3.0
2013-05-17T16:24:58.327Z
There is a [related paper](http://www.sciencedirect.com/science/article/pii/S0012365X13000046) that could be interesting in this context.
user13136
CC BY-SA 3.0
2013-05-16T16:52:59.700Z
2013-05-16T16:52:59.700Z
user13136
<p>An undirected graph $G$ is <a href="http://en.wikipedia.org/wiki/Chordal_graph">chordal</a> 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 <em>minimal separator</em> of $G$ if there exists $a$ and $b$ such that <strong>(i)</strong> $S$ disconnects $a$ from $b$ in $G$, and <strong>(ii)</strong> no proper subset of $S$ disconnects $a$ from $b$ in $G$.</p>

<p>A <a href="http://en.wikipedia.org/wiki/K-tree">$k$-tree</a> is a chordal graph where all maximal cliques are of size $k+1$ and all minimal separators of size $k$. A <a href="http://en.wikipedia.org/wiki/Block_graph">block graph</a> 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.</p>

<blockquote>
  <p>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?</p>
</blockquote>

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

<reference-request><graph-theory>
Does a chordal graph where the size of minimal separators is constrained have name?
Juho
# Does a chordal graph where the size of minimal separators is constrained have name?

(Asked by: username_0 on 2013-05-16)

An undirected graph $G$ is [chordal](http://en.wikipedia.org/wiki/Chordal_graph) 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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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$?

**Tags:** reference-request, graph-theory


---

## 2 answers

### Answer by username_1 on 2013-05-16. Score: 9 | Accepted answer

In [this paper](http://www.sciencedirect.com/science/article/pii/S0166218X11000424) 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.

> **Comments:**
> **username_1**: There is a [related paper](http://www.sciencedirect.com/science/article/pii/S0012365X13000046) that could be interesting in this context.  

---

### Answer by username_0 on 2013-05-31. Score: 4

[Kumar, P. S., & Madhavan, C. E. (1998). Minimal vertex separators of chordal graphs. Discrete Applied Mathematics, 89(1), 155-168](http://www.sciencedirect.com/science/article/pii/S0166218X98001231) 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](http://www.sciencedirect.com/science/article/pii/S0166218X0000336X) the same authors discuss $k$-separator-chordal graphs more in a slightly different context. See Section 6.2 in the paper.


---

