On $2$-extendability of generalized Petersen graphs

Nirmala B. Limaye; Mulupuri Shanthi C. Rao

Displaying similar documents to “On $2$ -extendability of generalized Petersen graphs”

On $r$ -extendability of the hypercube $Q_{n}$

Nirmala B. Limaye, Dinesh G. Sarvate (1997)

Mathematica Bohemica

Similarity:

A graph having a perfect matching is called $r$ -extendable if every matching of size $r$ can be extended to a perfect matching. It is proved that in the hypercube $Q_{n}$ , a matching $S$ with $| S | \leq n$ can be extended to a perfect matching if and only if it does not saturate the neighbourhood of any unsaturated vertex. In particular, $Q_{n}$ is $r$ -extendable for every $r$ with $1 \leq r \leq n - 1 .$

The directed distance dimension of oriented graphs

Gary Chartrand, Michael Raines, Ping Zhang (2000)

Mathematica Bohemica

Similarity:

For a vertex $v$ of a connected oriented graph $D$ and an ordered set $W = {w_{1}, w_{2}, \dots, w_{k}}$ of vertices of $D$ , the (directed distance) representation of $v$ with respect to $W$ is the ordered $k$ -tuple $r (v | W) = (d (v, w_{1}), d (v, w_{2}), \dots, d (v, w_{k}))$ , where $d (v, w_{i})$ is the directed distance from $v$ to $w_{i}$ . The set $W$ is a resolving set for $D$ if every two distinct vertices of $D$ have distinct representations. The minimum cardinality of a resolving set for $D$ is the (directed distance) dimension $dim (D)$ of $D$ . The dimension of a connected oriented graph need not be defined. Those oriented...

Exact $2$ -step domination in graphs

Gary Chartrand, Frank Harary, Moazzem Hossain, Kelly Schultz (1995)

Mathematica Bohemica

Similarity:

For a vertex $v$ in a graph $G$ , the set $N_{2} (v)$ consists of those vertices of $G$ whose distance from $v$ is 2. If a graph $G$ contains a set $S$ of vertices such that the sets $N_{2} (v)$ , $v \in S$ , form a partition of $V (G)$ , then $G$ is called a $2$ -step domination graph. We describe $2$ -step domination graphs possessing some prescribed property. In addition, all $2$ -step domination paths and cycles are determined.

Location-domatic number of a graph

Bohdan Zelinka (1998)

Mathematica Bohemica

Similarity:

A subset $D$ of the vertex set $V (G)$ of a graph $G$ is called locating-dominating, if for each $x \in V (G) - D$ there exists a vertex $y \to D$ adjacent to $x$ and for any two distinct vertices $x_{1}$ , $x_{2}$ of $V (G) - D$ the intersections of $D$ with the neighbourhoods of $x_{1}$ and $x_{2}$ are distinct. The maximum number of classes of a partition of $V (G)$ whose classes are locating-dominating sets in $G$ is called the location-domatic number of $G .$ Its basic properties are studied.

Stratidistance in stratified graphs

Gary Chartrand, Heather Gavlas, Michael A. Henning, Reza Rashidi (1997)

Mathematica Bohemica

Similarity:

A graph $G$ is a stratified graph if its vertex set is partitioned into classes (each of which is a stratum or a color class). A stratified graph with $k$ strata is $k$ -stratified. If $G$ is a connected $k$ -stratified graph with strata $S_{i}$ $(1 \leq i \leq k)$ where the vertices of $S_{i}$ are colored $X_{i}$ $(1 \leq i \leq k)$ , then the $X_{i}$ -proximity $ρ_{X_{i}} (v)$ of a vertex $v$ of $G$ is the distance between $v$ and a vertex of $S_{i}$ closest to $v$ . The strati-eccentricity $s e (v)$ of $v$ is $max {ρ_{X_{i}} (v) ∣ 1 \leq i \leq k}$ . The minimum strati-eccentricity over all vertices...

Displaying similar documents to “On 2 -extendability of generalized Petersen graphs”

On r -extendability of the hypercube Q n

The directed distance dimension of oriented graphs

Exact 2 -step domination in graphs

Location-domatic number of a graph

Stratidistance in stratified graphs

Displaying similar documents to “On $2$ -extendability of generalized Petersen graphs”

On $r$ -extendability of the hypercube $Q_{n}$

Exact $2$ -step domination in graphs