4
$\begingroup$

A subset $D$ of the vertices of a graph G is called a dominating set if every vertex of $G - D$ is adjacent to a vertex of $D$, and the domination number of $G$, denoted $\gamma(G)$, is the minimum cardinality of a dominating set.

The following article proves that any planar graph with diameter 2 has domination number at most 3.

  • MacGillivray G, Seyffarth K. Domination numbers of planar graphs[J]. Journal of Graph Theory, 1996, 22(3): 213-229.

As part of the proof, the authors also showed that planar graphs with minimum degree 5 of diameter two have domination number at most three. But the author did not construct the corresponding example graph.

My question is

  • whether a planar graph with minimum degree of 5 having diameter 2 exists. (Of course, it is better to construct a class of there graphs)

Another question is

  • whether a planar graph with minimum degree of 5 of diameter 2 having domination number three exists. (Of course, it is better to construct a class of there graphs)

I am aware that there are some planar graphs with minimum degree 5 of diameter 3 (see an icosahedron graph as a example).

enter image description here

Or we can see that some planar graphs with minimum degree 4 of diameter 2 (see an octahedral graph as a example).

enter image description here

$\endgroup$

1 Answer 1

2
$\begingroup$

The answer to the first question:

There is no planar graph of diameter two with minimal degree $5$. This follows from Seyffarth theorem, which is formulated as follows.

Let $G$ be a maximal planar graph with maximum degree $\Delta$ and diameter two. Then the minimum degree $\delta<5$ (Theorem 2), p.623.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .