Closed k-stop distance in graphs

Grady Bullington; Linda Eroh; Ralucca Gera; Steven J. Winters

Displaying similar documents to “Closed k-stop distance in graphs”

Radio number for some thorn graphs

Ruxandra Marinescu-Ghemeci (2010)

Discussiones Mathematicae Graph Theory

Similarity:

For a graph G and any two vertices u and v in G, let d(u,v) denote the distance between u and v and let diam(G) be the diameter of G. A multilevel distance labeling (or radio labeling) for G is a function f that assigns to each vertex of G a positive integer such that for any two distinct vertices u and v, d(u,v) + |f(u) - f(v)| ≥ diam(G) + 1. The largest integer in the range of f is called the span of f and is denoted span(f). The radio number of G, denoted rn(G), is the minimum span...

Cores and shells of graphs

Allan Bickle (2013)

Mathematica Bohemica

Similarity:

The $k$ -core of a graph $G$ , $C_{k} (G)$ , is the maximal induced subgraph $H \subseteq G$ such that $δ (G) \geq k$ , if it exists. For $k > 0$ , the $k$ -shell of a graph $G$ is the subgraph of $G$ induced by the edges contained in the $k$ -core and not contained in the $(k + 1)$ -core. The core number of a vertex is the largest value for $k$ such that $v \in C_{k} (G)$ , and the maximum core number of a graph, $\hat{C} (G)$ , is the maximum of the core numbers of the vertices of $G$ . A graph $G$ is $k$ -monocore if $\hat{C} (G) = δ (G) = k$ . This paper discusses some basic results on the structure of $k$ -cores and...

On integral sum graphs with a saturated vertex

Zhibo Chen (2010)

Czechoslovak Mathematical Journal

Similarity:

As introduced by F. Harary in 1994, a graph $G$ is said to be an $i n t e g r a l$ $s u m$ $g r a p h$ if its vertices can be given a labeling $f$ with distinct integers so that for any two distinct vertices $u$ and $v$ of $G$ , $u v$ is an edge of $G$ if and only if $f (u) + f (v) = f (w)$ for some vertex $w$ in $G$ . We prove that every integral sum graph with a saturated vertex, except the complete graph $K_{3}$ , has edge-chromatic number equal to its maximum degree. (A vertex of a graph $G$ is said to be if it is adjacent to every...

Minimum degree, leaf number and traceability

Simon Mukwembi (2013)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a finite connected graph with minimum degree $δ$ . The leaf number $L (G)$ of $G$ is defined as the maximum number of leaf vertices contained in a spanning tree of $G$ . We prove that if $δ \geq \frac{1}{2} (L (G) + 1)$ , then $G$ is 2-connected. Further, we deduce, for graphs of girth greater than 4, that if $δ \geq \frac{1}{2} (L (G) + 1)$ , then $G$ contains a spanning path. This provides a partial solution to a conjecture of the computer program Graffiti.pc [DeLaVi na and Waller, Spanning trees with many leaves and average distance, Electron. J. Combin....

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...