Stratidistance in stratified graphs

Gary Chartrand; Heather Gavlas; Michael A. Henning; Reza Rashidi

Displaying similar documents to “Stratidistance in stratified graphs”

Distance in stratified graphs

Gary Chartrand, Lisa Hansen, Reza Rashidi, Naveed Sherwani (2000)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is stratified if its vertex set is partitioned into classes, called strata. If there are $k$ strata, then $G$ is $k$ -stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color $X$ in a stratified graph $G$ , the $X$ -eccentricity $e_{X} (v)$ of a vertex $v$ of $G$ is the distance between $v$ and an $X$ -colored vertex furthest from $v$ . The minimum $X$ -eccentricity among the vertices of $G$ is the $X$ -radius ${r a d}_{X} G$ of $G$ ...

Coalescing Fiedler and core vertices

Didar A. Ali, John Baptist Gauci, Irene Sciriha, Khidir R. Sharaf (2016)

Czechoslovak Mathematical Journal

Similarity:

The nullity of a graph $G$ is the multiplicity of zero as an eigenvalue in the spectrum of its adjacency matrix. From the interlacing theorem, derived from Cauchy’s inequalities for matrices, a vertex of a graph can be a core vertex if, on deleting the vertex, the nullity decreases, or a Fiedler vertex, otherwise. We adopt a graph theoretical approach to determine conditions required for the identification of a pair of prescribed types of root vertices of two graphs to form a cut-vertex...

A note on the independent domination number of subset graph

Xue-Gang Chen, De-xiang Ma, Hua Ming Xing, Liang Sun (2005)

Czechoslovak Mathematical Journal

Similarity:

The independent domination number $i (G)$ (independent number $β (G)$ ) is the minimum (maximum) cardinality among all maximal independent sets of $G$ . Haviland (1995) conjectured that any connected regular graph $G$ of order $n$ and degree $δ \leq \frac{1}{2} n$ satisfies $i (G) \leq ⌈ \frac{2 n}{3 δ} ⌉ \frac{1}{2} δ$ . For $1 \leq k \leq l \leq m$ , the subset graph $S_{m} (k, l)$ is the bipartite graph whose vertices are the $k$ - and $l$ -subsets of an $m$ element ground set where two vertices are adjacent if and only if one subset is contained in the other. In this paper, we give a sharp upper bound for $i (S_{m} (k, l))$ and...

Domination in partitioned graphs

Zsolt Tuza, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Similarity:

Let V₁, V₂ be a partition of the vertex set in a graph G, and let $γ_{i}$ denote the least number of vertices needed in G to dominate $V_{i}$ . We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest...

A note on periodicity of the 2-distance operator

Bohdan Zelinka (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The paper solves one problem by E. Prisner concerning the 2-distance operator T₂. This is an operator on the class $C_{f}$ of all finite undirected graphs. If G is a graph from $C_{f}$ , then T₂(G) is the graph with the same vertex set as G in which two vertices are adjacent if and only if their distance in G is 2. E. Prisner asks whether the periodicity ≥ 3 is possible for T₂. In this paper an affirmative answer is given. A result concerning the periodicity 2 is added.

Homogeneously embedding stratified graphs in stratified graphs

Gary Chartrand, Donald W. Vanderjagt, Ping Zhang (2005)

Mathematica Bohemica

Similarity:

A 2-stratified graph $G$ is a graph whose vertex set has been partitioned into two subsets, called the strata or color classes of $G$ . Two $2$ -stratified graphs $G$ and $H$ are isomorphic if there exists a color-preserving isomorphism $φ$ from $G$ to $H$ . A $2$ -stratified graph $G$ is said to be homogeneously embedded in a $2$ -stratified graph $H$ if for every vertex $x$ of $G$ and every vertex $y$ of $H$ , where $x$ and $y$ are colored the same, there exists an induced $2$ -stratified subgraph $H^{'}$ of $H$ containing $y$ and a color-preserving...

Domination Subdivision Numbers

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, David P. Jacobs, James Knisely, Lucas C. van der Merwe (2001)

Discussiones Mathematicae Graph Theory

Similarity:

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number $s d_{γ} (G)$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that $1 \leq s d_{γ} (G) \leq 3$ for any graph G. We give a counterexample to this conjecture. On the other hand,...