Paths with restricted degrees of their vertices in planar graphs

Stanislav Jendroľ

Displaying similar documents to “Paths with restricted degrees of their vertices in planar graphs”

The eavesdropping number of a graph

Jeffrey L. Stuart (2009)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a connected, undirected graph without loops and without multiple edges. For a pair of distinct vertices $u$ and $v$ , a minimum ${u, v}$ -separating set is a smallest set of edges in $G$ whose removal disconnects $u$ and $v$ . The edge connectivity of $G$ , denoted $λ (G)$ , is defined to be the minimum cardinality of a minimum ${u, v}$ -separating set as $u$ and $v$ range over all pairs of distinct vertices in $G$ . We introduce and investigate the eavesdropping number, denoted $ε (G)$ , which is defined to be the maximum cardinality...

The independent resolving number of a graph

Gary Chartrand, Varaporn Saenpholphat, Ping Zhang (2003)

Mathematica Bohemica

Similarity:

For an ordered set $W = {w_{1}, w_{2}, \dots, w_{k}}$ of vertices in a connected graph $G$ and a vertex $v$ of $G$ , the code of $v$ with respect to $W$ is the $k$ -vector $c_{W} (v) = (d (v, w_{1}), d (v, w_{2}), \dots, d (v, w_{k})) .$ The set $W$ is an independent resolving set for $G$ if (1) $W$ is independent in $G$ and (2) distinct vertices have distinct codes with respect to $W$ . The cardinality of a minimum independent resolving set in $G$ is the independent resolving number $i r (G)$ . We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs $G$ of order...

Bounds concerning the alliance number

Grady Bullington, Linda Eroh, Steven J. Winters (2009)

Mathematica Bohemica

Similarity:

P. Kristiansen, S. M. Hedetniemi, and S. T. Hedetniemi, in Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004), 157–177, and T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, in Global defensive alliances in graphs, Electron. J. Combin. 10 (2003), introduced the defensive alliance number $a (G)$ , strong defensive alliance number $\hat{a} (G)$ , and global defensive alliance number $γ_{a} (G)$ . In this paper, we consider relationships between these parameters and the domination number $γ (G)$ . For any positive...