Displaying similar documents to “On signpost systems and connected graphs”

The induced paths in a connected graph and a ternary relation determined by them

Ladislav Nebeský (2002)

Mathematica Bohemica

Similarity:

By a ternary structure we mean an ordered pair ( X 0 , T 0 ) , where X 0 is a finite nonempty set and T 0 is a ternary relation on X 0 . By the underlying graph of a ternary structure ( X 0 , T 0 ) we mean the (undirected) graph G with the properties that X 0 is its vertex set and distinct vertices u and v of G are adjacent if and only if { x X 0 T 0 ( u , x , v ) } { x X 0 T 0 ( v , x , u ) } = { u , v } . A ternary structure ( X 0 , T 0 ) is said to be the B-structure of a connected graph G if X 0 is the vertex set of G and the following statement holds for all u , x , y X 0 : T 0 ( x , u , y ) if and only if u belongs to an...

Iterated neighborhood graphs

Martin Sonntag, Hanns-Martin Teichert (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph ( V , E N ) where E N = a,b | a ≠ b, x,a ∈ E and x,b ∈ E for some x ∈ V. It is well-known that the neighborhood graph N(G) is connected if and only if the graph G is connected and non-bipartite. We present some results concerning the k-iterated neighborhood graph N k ( G ) : = N ( N ( . . . N ( G ) ) ) of G. In particular we investigate conditions for G and k such that N k ( G ) becomes a complete graph.

Histories in path graphs

Ludovít Niepel (2007)

Discussiones Mathematicae Graph Theory

Similarity:

For a given graph G and a positive integer r the r-path graph, P r ( G ) , has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length r-1, and their union forms either a cycle or a path of length k+1 in G. Let P r k ( G ) be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of P r k ( G ) . The k-history P r - k ( H ) is a subgraph of G that is induced by all edges that take part in the recursive...

Remarks on partially square graphs, hamiltonicity and circumference

Hamamache Kheddouci (2001)

Discussiones Mathematicae Graph Theory

Similarity:

Given a graph G, its partially square graph G* is a graph obtained by adding an edge (u,v) for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition N G ( x ) N G [ u ] N G [ v ] , where N G [ x ] = N G ( x ) x . In the case where G is a claw-free graph, G* is equal to G². We define σ ° = m i n x S d G ( x ) : S i s a n i n d e p e n d e n t s e t i n G * a n d | S | = t . We give for hamiltonicity and circumference new sufficient conditions depending on σ° and we improve some known results.

On the minus domination number of graphs

Hailong Liu, Liang Sun (2004)

Czechoslovak Mathematical Journal

Similarity:

Let G = ( V , E ) be a simple graph. A 3 -valued function f V ( G ) { - 1 , 0 , 1 } is said to be a minus dominating function if for every vertex v V , f ( N [ v ] ) = u N [ v ] f ( u ) 1 , where N [ v ] is the closed neighborhood of v . The weight of a minus dominating function f on G is f ( V ) = v V f ( v ) . The minus domination number of a graph G , denoted by γ - ( G ) , equals the minimum weight of a minus dominating function on G . In this paper, the following two results are obtained. (1) If G is a bipartite graph of order n , then γ - ( G ) 4 n + 1 - 1 - n . (2) For any negative integer k and any positive integer...

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.