Displaying similar documents to “On r -extendability of the hypercube Q n ”

Point-set domatic numbers of graphs

Bohdan Zelinka (1999)

Mathematica Bohemica

Similarity:

A subset D of the vertex set V ( G ) of a graph G is called point-set dominating, if for each subset S ⊆ V ( G ) - D there exists a vertex v ∈ D such that the subgraph of G induced by S ∪ { v } is connected. The maximum number of classes of a partition of V ( G ) , all of whose classes are point-set dominating sets, is the point-set domatic number d p ( G ) of G . Its basic properties are studied in the paper.

On 2 -extendability of generalized Petersen graphs

Nirmala B. Limaye, Mulupuri Shanthi C. Rao (1996)

Mathematica Bohemica

Similarity:

Let G P ( n , k ) be a generalized Petersen graph with ( n , k ) = 1 , n > k ≥ 4 . Then every pair of parallel edges of G P ( n , k ) is contained in a 1-factor of G P ( n , k ) . This partially answers a question posed by Larry Cammack and Gerald Schrag [Problem 101, Discrete Math. 73(3), 1989, 311-312].

Location-domatic number of a graph

Bohdan Zelinka (1998)

Mathematica Bohemica

Similarity:

A subset D of the vertex set V ( G ) of a graph G is called locating-dominating, if for each x ∈ V ( G ) - D there exists a vertex y → D adjacent to x and for any two distinct vertices x 1 , x 2 of V ( G ) - D the intersections of D with the neighbourhoods of x 1 and x 2 are distinct. The maximum number of classes of a partition of V ( G ) whose classes are locating-dominating sets in G is called the location-domatic number of G . Its basic properties are studied.

Circular distance in directed graphs

Bohdan Zelinka (1997)

Mathematica Bohemica

Similarity:

Circular distance d ∘ ( x , y ) between two vertices x , y of a strongly connected directed graph G is the sum d ( x , y ) + d ( y , x ) , where d is the usual distance in digraphs. Its basic properties are studied.