Currently displaying 1 – 20 of 239

Showing per page

Order by Relevance | Title | Year of publication

A note on periodicity of the 2-distance operator

Bohdan Zelinka — 2000

Discussiones Mathematicae Graph Theory

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.

On the simplex graph operator

Bohdan Zelinka — 1998

Discussiones Mathematicae Graph Theory

A simplex of a graph G is a subgraph of G which is a complete graph. The simplex graph Simp(G) of G is the graph whose vertex set is the set of all simplices of G and in which two vertices are adjacent if and only if they have a non-empty intersection. The simplex graph operator is the operator which to every graph G assigns its simplex graph Simp(G). The paper studies graphs which are fixed in this operator and gives a partial answer to a problem suggested by E. Prisner.

Signed total domination number of a graph

Bohdan Zelinka — 2001

Czechoslovak Mathematical Journal

The signed total domination number of a graph is a certain variant of the domination number. If v is a vertex of a graph G , then N ( v ) is its oper neighbourhood, i.e. the set of all vertices adjacent to v in G . A mapping f : V ( G ) → { - 1 , 1 } , where V ( G ) is the vertex set of G , is called a signed total dominating function (STDF) on G , if ∑ x ∈ N ( v ) f ( x ) ≥ 1 for each v ∈ V ( G ) . The minimum of values ∑ x ∈ V ( G ) f ( x ) , taken over all STDF’s of G , is called the signed total domination number of G and denoted by γ s t ( G ) . A theorem stating lower bounds for γ s t ( G ) is stated for the...

Domination in bipartite graphs and in their complements

Bohdan Zelinka — 2003

Czechoslovak Mathematical Journal

The domatic numbers of a graph G and of its complement G ¯ were studied by J. E. Dunbar, T. W. Haynes and M. A. Henning. They suggested four open problems. We will solve the following ones: Characterize bipartite graphs G having d ( G ) = d ( G ¯ ) . Further, we will present a partial solution to the problem: Is it true that if G is a graph satisfying d ( G ) = d ( G ¯ ) , then γ ( G ) = γ ( G ¯ ) ? Finally, we prove an existence theorem concerning the total domatic number of a graph and of its complement.

Domination in generalized Petersen graphs

Bohdan Zelinka — 2002

Czechoslovak Mathematical Journal

Generalized Petersen graphs are certain graphs consisting of one quadratic factor. For these graphs some numerical invariants concerning the domination are studied, namely the domatic number d ( G ) , the total domatic number d t ( G ) and the k -ply domatic number d k ( G ) for k = 2 and k = 3 . Some exact values and some inequalities are stated.

Edge domination in graphs of cubes

Bohdan Zelinka — 2002

Czechoslovak Mathematical Journal

The signed edge domination number and the signed total edge domination number of a graph are considered; they are variants of the domination number and the total domination number. Some upper bounds for them are found in the case of the n -dimensional cube Q n .

On a problem concerning k -subdomination numbers of graphs

Bohdan Zelinka — 2003

Czechoslovak Mathematical Journal

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 .

Page 1 Next

Download Results (CSV)