Displaying similar documents to “On k -strong distance in strong digraphs”

On a problem of E. Prisner concerning the biclique operator

Bohdan Zelinka (2002)

Mathematica Bohemica

Similarity:

The symbol K ( B , C ) denotes a directed graph with the vertex set B ∪ C for two (not necessarily disjoint) vertex sets B , C in which an arc goes from each vertex of B into each vertex of C . A subdigraph of a digraph D which has this form is called a bisimplex in D . A biclique in D is a bisimplex in D which is not a proper subgraph of any other and in which B ≠ ∅ and C ≠ ∅ . The biclique digraph C → ( D ) of D is the digraph whose vertex set is the set of all bicliques in D and in which there is an arc from K ( B 1 , C 1 ) into K ( B 2 , C 2 ) ...

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

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.

Decomposition of complete bipartite digraphs and even complete bipartite multigraphs into closed trails

Sylwia Cichacz (2007)

Discussiones Mathematicae Graph Theory

Similarity:

It has been shown [3] that any bipartite graph K a , b , where a, b are even integers, can be decomposed into closed trails with prescribed even lengths. In this article, we consider the corresponding question for directed bipartite graphs. We show that a complete directed bipartite graph ↔ K a , b is decomposable into directed closed trails of even lengths greater than 2, whenever these lengths sum up to the size of the digraph. We use this result to prove that complete bipartite multigraphs can be...

On arbitrarily vertex decomposable unicyclic graphs with dominating cycle

Sylwia Cichacz, Irmina A. Zioło (2006)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n₁,...,nₖ) of positive integers such that ∑ i = 1 k n i = n , there exists a partition (V₁,...,Vₖ) of vertex set of G such that for every i ∈ 1,...,k the set V i induces a connected subgraph of G on n i vertices. We consider arbitrarily vertex decomposable unicyclic graphs with dominating cycle. We also characterize all such graphs with at most four hanging vertices such that exactly two of them have a common neighbour. ...