Displaying similar documents to “Decomposing complete graphs into cubes”

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

On a problem concerning k -subdomination numbers of graphs

Bohdan Zelinka (2003)

Czechoslovak Mathematical Journal

Similarity:

One of numerical invariants concerning domination in graphs is the k -subdomination number γ k S - 11 ( G ) of a graph G . A conjecture concerning it was expressed by J. H. Hattingh, namely that for any connected graph G with n vertices and any k with 1 2 n < k ≦ n the inequality γ k S - 11 ( G ) ≦ 2 k - n holds. This paper presents a simple counterexample which disproves this conjecture. This counterexample is the graph of the three-dimensional cube and k = 5 .

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.

Counterexample to a conjecture on the structure of bipartite partitionable graphs

Richard G. Gibson, Christina M. Mynhardt (2007)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is called a prism fixer if γ(G×K₂) = γ(G), where γ(G) denotes the domination number of G. A symmetric γ-set of G is a minimum dominating set D which admits a partition D = D₁∪ D₂ such that V ( G ) - N [ D i ] = D j , i,j = 1,2, i ≠ j. It is known that G is a prism fixer if and only if G has a symmetric γ-set. Hartnell and Rall [On dominating the Cartesian product of a graph and K₂, Discuss. Math. Graph Theory 24 (2004), 389-402] conjectured that if G is a connected, bipartite graph such that V(G) can...

Decomposition of complete graphs into ( 0 , 2 ) -prisms

Sylwia Cichacz, Soleh Dib, Dalibor Fronček (2014)

Czechoslovak Mathematical Journal

Similarity:

R. Frucht and J. Gallian (1988) proved that bipartite prisms of order 2 n have an α -labeling, thus they decompose the complete graph K 6 n x + 1 for any positive integer x . We use a technique called the ρ + -labeling introduced by S. I. El-Zanati, C. Vanden Eynden, and N. Punnim (2001) to show that also some other families of 3-regular bipartite graphs of order 2 n called generalized prisms decompose the complete graph K 6 n x + 1 for any positive integer x .

Graceful signed graphs

Mukti Acharya, Tarkeshwar Singh (2004)

Czechoslovak Mathematical Journal

Similarity:

A ( p , q ) -sigraph S is an ordered pair ( G , s ) where G = ( V , E ) is a ( p , q ) -graph and s is a function which assigns to each edge of G a positive or a negative sign. Let the sets E + and E - consist of m positive and n negative edges of G , respectively, where m + n = q . Given positive integers k and d , S is said to be ( k , d ) -graceful if the vertices of G can be labeled with distinct integers from the set { 0 , 1 , ⋯ , k + ( q - 1 ) d } such that when each edge u v of G is assigned the product of its sign and the absolute difference of the integers assigned to...

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.