Displaying similar documents to “Remarks on partially square graphs, hamiltonicity and circumference”

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.

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.

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

Potentially H-bigraphic sequences

Michael Ferrara, Michael Jacobson, John Schmitt, Mark Siggers (2009)

Discussiones Mathematicae Graph Theory

Similarity:

We extend the notion of a potentially H-graphic sequence as follows. Let A and B be nonnegative integer sequences. The sequence pair S = (A,B) is said to be bigraphic if there is some bipartite graph G = (X ∪ Y,E) such that A and B are the degrees of the vertices in X and Y, respectively. If S is a bigraphic pair, let σ(S) denote the sum of the terms in A. Given a bigraphic pair S, and a fixed bipartite graph H, we say that S is potentially H-bigraphic if there is some realization of...

Intersection graph of gamma sets in the total graph

T. Tamizh Chelvam, T. Asir (2012)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we consider the intersection graph I Γ ( ) of gamma sets in the total graph on ℤₙ. We characterize the values of n for which I Γ ( ) is complete, bipartite, cycle, chordal and planar. Further, we prove that I Γ ( ) is an Eulerian, Hamiltonian and as well as a pancyclic graph. Also we obtain the value of the independent number, the clique number, the chromatic number, the connectivity and some domination parameters of I Γ ( ) .

On the order of certain close to regular graphs without a matching of given size

Sabine Klinkenberg, Lutz Volkmann (2007)

Czechoslovak Mathematical Journal

Similarity:

A graph G is a { d , d + k } -graph, if one vertex has degree d + k and the remaining vertices of G have degree d . In the special case of k = 0 , the graph G is d -regular. Let k , p 0 and d , n 1 be integers such that n and p are of the same parity. If G is a connected { d , d + k } -graph of order n without a matching M of size 2 | M | = n - p , then we show in this paper the following: If d = 2 , then k 2 ( p + 2 ) and (i) n k + p + 6 . If d 3 is odd and t an integer with 1 t p + 2 , then (ii) n d + k + 1 for k d ( p + 2 ) , (iii) n d ( p + 3 ) + 2 t + 1 for d ( p + 2 - t ) + t k d ( p + 3 - t ) + t - 3 , (iv) n d ( p + 3 ) + 2 p + 7 for k p . If d 4 is even, then (v) n d + k + 2 - η for k d ( p + 3 ) + p + 4 + η , (vi) n d + k + p + 2 - 2 t = d ( p + 4 ) + p + 6 for k = d ( p + 3 ) + 4 + 2 t and p 1 ,...

On light subgraphs in plane graphs of minimum degree five

Stanislav Jendrol', Tomáš Madaras (1996)

Discussiones Mathematicae Graph Theory

Similarity:

A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is well known that a plane graph of minimum degree five contains light edges and light triangles. In this paper we show that every plane graph of minimum degree five contains also light stars K 1 , 3 and K 1 , 4 and a light 4-path P₄. The results obtained for K 1 , 3 and P₄ are best possible.

4-cycle properties for characterizing rectagraphs and hypercubes

Khadra Bouanane, Abdelhafid Berrachedi (2017)

Czechoslovak Mathematical Journal

Similarity:

A ( 0 , 2 ) -graph is a connected graph, where each pair of vertices has either 0 or 2 common neighbours. These graphs constitute a subclass of ( 0 , λ ) -graphs introduced by Mulder in 1979. A rectagraph, well known in diagram geometry, is a triangle-free ( 0 , 2 ) -graph. ( 0 , 2 ) -graphs include hypercubes, folded cube graphs and some particular graphs such as icosahedral graph, Shrikhande graph, Klein graph, Gewirtz graph, etc. In this paper, we give some local properties of 4-cycles in ( 0 , λ ) -graphs and more specifically...

On 𝓕-independence in graphs

Frank Göring, Jochen Harant, Dieter Rautenbach, Ingo Schiermeyer (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let be a set of graphs and for a graph G let α ( G ) and α * ( G ) denote the maximum order of an induced subgraph of G which does not contain a graph in as a subgraph and which does not contain a graph in as an induced subgraph, respectively. Lower bounds on α ( G ) and α * ( G ) are presented.

On the total k-domination number of graphs

Adel P. Kazemi (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let k be a positive integer and let G = (V,E) be a simple graph. The k-tuple domination number γ × k ( G ) of G is the minimum cardinality of a k-tuple dominating set S, a set that for every vertex v ∈ V, | N G [ v ] S | k . Also the total k-domination number γ × k , t ( G ) of G is the minimum cardinality of a total k -dominating set S, a set that for every vertex v ∈ V, | N G ( v ) S | k . The k-transversal number τₖ(H) of a hypergraph H is the minimum size of a subset S ⊆ V(H) such that |S ∩e | ≥ k for every edge e ∈ E(H). We know that for...

Domination and independence subdivision numbers of graphs

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The domination subdivision number s d γ ( G ) of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of...

The Wiener number of powers of the Mycielskian

Rangaswami Balakrishnan, S. Francis Raj (2010)

Discussiones Mathematicae Graph Theory

Similarity:

The Wiener number of a graph G is defined as 1 / 2 u , v V ( G ) d ( u , v ) , d the distance function on G. The Wiener number has important applications in chemistry. We determine a formula for the Wiener number of an important graph family, namely, the Mycielskians μ(G) of graphs G. Using this, we show that for k ≥ 1, W ( μ ( S k ) ) W ( μ ( T k ) ) W ( μ ( P k ) ) , where Sₙ, Tₙ and Pₙ denote a star, a general tree and a path on n vertices respectively. We also obtain Nordhaus-Gaddum type inequality for the Wiener number of μ ( G k ) .

Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs

Éric Sopena (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The oriented chromatic number of an oriented graph G is the minimum order of an oriented graph H such that G admits a homomorphism to H . The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph U such that every orientation G of G admits a homomorphism to U . We give...

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 s d γ ( G ) 3 for any graph G. We give a counterexample to this conjecture. On the other hand,...