Advanced Search

Bipartite graphs with equal edge domination number and maximum matching cardinality are characterized. These two parameters are used to develop bounds on the vertex cover and total vertex cover numbers of graphs and a resulting chain of vertex covering, edge domination, and matching parameters is explored. In addition, the total vertex cover number is compared to the total domination number of trees and grid graphs.

For each vertex v in a graph G, let there be associated a subgraph $H_v$ of G. The vertex v is said to dominate $H_v$ as well as dominate each vertex and edge of $H_v$. A set S of vertices of G is called a full dominating set if every vertex of G is dominated by some vertex of S, as is every edge of G. The minimum cardinality of a full dominating set of G is its full domination number ${\gamma }_{FH}\left(G\right)$. A full dominating set of G of cardinality ${\gamma }_{FH}\left(G\right)$ is called a ${\gamma }_{FH}$-set of G. We study three types of full domination in graphs: full...

For an ordered set $W=\{w_1,w_2,\cdots ,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$, the (metric) representation of $v$ with respect to $W$ is the $k$-vector $r\left(v\right|W)=(d(v,w_1),d(v,w_2),\cdots ,d(v,w_k))$, where $d(x,y)$ represents the distance between the vertices $x$ and $y$. The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$. A resolving set of minimum cardinality is called a minimum resolving set or a basis and the cardinality of a basis for $G$ is its dimension $dimG$. A set $S$ of vertices in $G$ is a dominating set...