1
$\begingroup$

Let $\gamma(G)$ be the domination number of a graph $G$. I was wondering if there is special terminology for graphs with $\gamma(G)=1$? Examples of graphs with $\gamma(G)=1$ include $K_{1,n}$ and Wheel graphs.

$\endgroup$
2
  • 1
    $\begingroup$ In other words, graphs obtained by adding edges to a star graph? $\endgroup$ Commented Sep 3, 2021 at 12:42
  • $\begingroup$ @HagenvonEitzen, exactly! Subgraphs of a complete graph on $n$ vertices that have a star graph as a subgraph. $\endgroup$
    – Math137
    Commented Sep 3, 2021 at 12:57

1 Answer 1

1
$\begingroup$

I really did not expect this to have a term, but according to Wikipedia:

  • If $G$ has a dominating set $\{v\}$, $v$ is called a universal vertex or dominating vertex;
  • $G$ itself is called a cone when it has a dominating vertex.

Wikipedia is iffy about calling $v$ the apex of the cone, because this conflicts with other terminology, but apparently this is also a thing sometimes.

We can be more precise than calling $G$ a cone. In sources like this paper, for any graph $G$, we can construct the cone of $G$, denoted $CG$, by adding a new vertex adjacent to all vertices of $G$.

There is, however, another notion of cone graph which refers to a more specific graph (which is only sometimes a cone in the above terminology).

$\endgroup$

You must log in to answer this question.

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