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

On integral sum graphs with a saturated vertex

Zhibo Chen (2010)

Czechoslovak Mathematical Journal

Similarity:

As introduced by F. Harary in 1994, a graph G is said to be an i n t e g r a l s u m g r a p h if its vertices can be given a labeling f with distinct integers so that for any two distinct vertices u and v of G , u v is an edge of G if and only if f ( u ) + f ( v ) = f ( w ) for some vertex w in G . We prove that every integral sum graph with a saturated vertex, except the complete graph K 3 , has edge-chromatic number equal to its maximum degree. (A vertex of a graph G is said to be if it is adjacent to every...

A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs

Wojciech Wideł (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies [...] min⁡dG(u),dG(v)≥n+12 min { d G ( u ) , d G ( v ) } ≥ n + 1 2 . In this paper we prove that every 2-connected K1,3, P5-f1-heavy graph is pancyclic. This result completes the answer to the problem of finding f1-heavy pairs of subgraphs implying...