Displaying similar documents to “Locally regular graphs”

Two classes of graphs related to extremal eccentricities

Ferdinand Gliviak (1997)

Mathematica Bohemica

Similarity:

A graph G is called an S -graph if its periphery P e r i ( G ) is equal to its center eccentric vertices C e p ( G ) . Further, a graph G is called a D -graph if P e r i ( G ) ∩ C e p ( G ) = ∅ . We describe S -graphs and D -graphs for small radius. Then, for a given graph H and natural numbers r ≥ 2 , n ≥ 2 , we construct an S -graph of radius r having n central vertices and containing H as an induced subgraph. We prove an analogous existence theorem for D -graphs, too. At the end, we give some properties of S -graphs and D -graphs.

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.

Exact 2 -step domination in graphs

Gary Chartrand, Frank Harary, Moazzem Hossain, Kelly Schultz (1995)

Mathematica Bohemica

Similarity:

For a vertex v in a graph G , the set N 2 ( v ) consists of those vertices of G whose distance from v is 2. If a graph G contains a set S of vertices such that the sets N 2 ( v ) , v ∈ S , form a partition of V ( G ) , then G is called a 2 -step domination graph. We describe 2 -step domination graphs possessing some prescribed property. In addition, all 2 -step domination paths and cycles are determined.

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.

Stratidistance in stratified graphs

Gary Chartrand, Heather Gavlas, Michael A. Henning, Reza Rashidi (1997)

Mathematica Bohemica

Similarity:

A graph G is a stratified graph if its vertex set is partitioned into classes (each of which is a stratum or a color class). A stratified graph with k strata is k -stratified. If G is a connected k -stratified graph with strata S i ( 1 ≤ i ≤ k ) where the vertices of S i are colored X i ( 1 ≤ i ≤ k ) , then the X i -proximity ρ X i ( v ) of a vertex v of G is the distance between v and a vertex of S i closest to v . The strati-eccentricity s e ( v ) of v is max { ρ X i ( v ) ∣ 1 ≤ i ≤ k } . The minimum strati-eccentricity over all vertices...

A note on the independent domination number of subset graph

Xue-Gang Chen, De-xiang Ma, Hua Ming Xing, Liang Sun (2005)

Czechoslovak Mathematical Journal

Similarity:

The independent domination number i ( G ) (independent number β ( G ) ) is the minimum (maximum) cardinality among all maximal independent sets of G . Haviland (1995) conjectured that any connected regular graph G of order n and degree δ ≤ 1 2 n satisfies i ( G ) ≤ ⌈ 2 n 3 δ ⌉ 1 2 δ . For 1 ≤ k ≤ l ≤ m , the subset graph S m ( k , l ) is the bipartite graph whose vertices are the k - and l -subsets of an m element ground set where two vertices are adjacent if and only if one subset is contained in the other. In this paper, we give a sharp upper bound for i ( S m ( k , l ) ) and...