Displaying similar documents to “Digraphs with isomorphic underlying and domination graphs: connected U G c ( d ) ”

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.

On infinite uniquely partitionable graphs and graph properties of finite character

Jozef Bucko, Peter Mihók (2009)

Discussiones Mathematicae Graph Theory

Similarity:

A graph property is any nonempty isomorphism-closed class of simple (finite or infinite) graphs. A graph property is of finite character if a graph G has a property if and only if every finite induced subgraph of G has a property . Let ₁,₂,...,ₙ be graph properties of finite character, a graph G is said to be (uniquely) (₁, ₂, ...,ₙ)-partitionable if there is an (exactly one) partition V₁, V₂, ..., Vₙ of V(G) such that G [ V i ] ∈ i for i = 1,2,...,n. Let us denote by ℜ = ₁ ∘ ₂ ∘ ... ∘ ₙ the class...

On well-covered graphs of odd girth 7 or greater

Bert Randerath, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Similarity:

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth...

Cores and shells of graphs

Allan Bickle (2013)

Mathematica Bohemica

Similarity:

The k -core of a graph G , C k ( G ) , is the maximal induced subgraph H ⊆ G such that δ ( G ) ≥ k , if it exists. For k > 0 , the k -shell of a graph G is the subgraph of G induced by the edges contained in the k -core and not contained in the ( k + 1 ) -core. The core number of a vertex is the largest value for k such that v ∈ C k ( G ) , and the maximum core number of a graph, C ^ ( G ) , is the maximum of the core numbers of the vertices of G . A graph G is k -monocore if C ^ ( G ) = δ ( G ) = k . This paper discusses some basic results on the structure of k -cores and...

Graphs with the same peripheral and center eccentric vertices

Peter Kyš (2000)

Mathematica Bohemica

Similarity:

The eccentricity e ( v ) of a vertex v is the distance from v to a vertex farthest from v , and u is an eccentric vertex for v if its distance from v is d ( u , v ) = e ( v ) . A vertex of maximum eccentricity in a graph G is called peripheral, and the set of all such vertices is the peripherian, denoted P e r i G ) . We use C e p ( G ) to denote the set of eccentric vertices of vertices in C ( G ) . A graph G is called an S-graph if C e p ( G ) = P e r i ( G ) . In this paper we characterize S-graphs with diameters less or equal to four, give some constructions of...