Equality in a Linear Vizing-Like Relation that Relates the Size and Total Domination Number of a Graph

Details Equality in a Linear Vizing-Like Relation that Relates the Size and Total Domination Number of a Graph Equality in a Linear Vizing-Like Relation that Relates the Size and Total Domination Number of a Graph

2011-08-30

arxiv.org/abs/1108.5949v1

Mathematics

Combinatorics

15 pages

Scientific paper

Let $G$ be a graph each component of which has order at least 3, and let $G$ have order $n$, size $m$, total domination number $\gamma_t$ and maximum degree $\Delta(G)$. Let $\Delta = 3$ if $\Delta(G) = 2$ and $\Delta = \Delta (G)$ if $\Delta(G) \ge 3$. It is known [J. Graph Theory 49 (2005), 285--290; J. Graph Theory 54 (2007), 350--353] that $m \le \Delta (n- \gamma_t)$. In this paper we characterize the extremal graphs $G$ satisfying $m = \Delta (n- \gamma_t)$.

Affiliated with

Also associated with

No associations

Rating

Equality in a Linear Vizing-Like Relation that Relates the Size and Total Domination Number of a Graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Equality in a Linear Vizing-Like Relation that Relates the Size and Total Domination Number of a Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Equality in a Linear Vizing-Like Relation that Relates the Size and Total Domination Number of a Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-729042