Displaying similar documents to “A note on maximal common subgraphs of the Dirac's family of graphs”

Maximal graphs with respect to hereditary properties

Izak Broere, Marietjie Frick, Gabriel Semanišin (1997)

Discussiones Mathematicae Graph Theory

Similarity:

A property of graphs is a non-empty set of graphs. A property P is called hereditary if every subgraph of any graph with property P also has property P. Let P₁, ...,Pₙ be properties of graphs. We say that a graph G has property P₁∘...∘Pₙ if the vertex set of G can be partitioned into n sets V₁, ...,Vₙ such that the subgraph of G induced by Vi has property P i ; i = 1,..., n. A hereditary property R is said to be reducible if there exist two hereditary properties P₁ and P₂ such that R =...

Edge maximal C 2 k + 1 -edge disjoint free graphs

M.S.A. Bataineh, M.M.M. Jaradat (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For two positive integers r and s, 𝓖(n;r,s) denotes to the class of graphs on n vertices containing no r of s-edge disjoint cycles and f(n;r,s) = max{𝓔(G):G ∈ 𝓖(n;r,s)}. In this paper, for integers r ≥ 2 and k ≥ 1, we determine f(n;r,2k+1) and characterize the edge maximal members in 𝓖(n;r,2k+1).

Bounding the Openk-Monopoly Number of Strong Product Graphs

Dorota Kuziak, Iztok Peterin, Ismael G. Yero (2018)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V, E) be a simple graph without isolated vertices and minimum degree δ, and let k ∈ 1 − ⌈δ/2⌉, . . . , ⌊δ/2⌋ be an integer. Given a set M ⊂ V, a vertex v of G is said to be k-controlled by M if [...] δM(v)≥δG(v)2+k δ M ( v ) δ G ( v ) 2 + k , where δM(v) represents the number of neighbors of v in M and δG(v) the degree of v in G. A set M is called an open k-monopoly if every vertex v of G is k-controlled by M. The minimum cardinality of any open k-monopoly is the open k-monopoly number of G. In this...

A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs

Yury Metelsky, Kseniya Schemeleva, Frank Werner (2017)

Discussiones Mathematicae Graph Theory

Similarity:

We characterize the class [...] L32 L 3 2 of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from [...] L32 L 3 2 in the class of threshold graphs, where n is the number of vertices of a tested graph.

Clopen graphs

Stefan Geschke (2013)

Fundamenta Mathematicae

Similarity:

A graph G on a topological space X as its set of vertices is clopen if the edge relation of G is a clopen subset of X² without the diagonal. We study clopen graphs on Polish spaces in terms of their finite induced subgraphs and obtain information about their cochromatic numbers. In this context we investigate modular profinite graphs, a class of graphs obtained from finite graphs by taking inverse limits. This continues the investigation of continuous colorings on Polish spaces and their...

On graphs with maximum size in their switching classes

Sergiy Kozerenko (2015)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

In his PhD thesis [Structural aspects of switching classes, Leiden Institute of Advanced Computer Science, 2001] Hage posed the following problem: “characterize the maximum size graphs in switching classes”. These are called s-maximal graphs. In this paper, we study the properties of such graphs. In particular, we show that any graph with sufficiently large minimum degree is s-maximal, we prove that join of two s-maximal graphs is also an s-maximal graph, we give complete characterization...

Forbidden triples implying Hamiltonicity: for all graphs

Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson (2004)

Discussiones Mathematicae Graph Theory

Similarity:

In [2], Brousek characterizes all triples of graphs, G₁, G₂, G₃, with G i = K 1 , 3 for some i = 1, 2, or 3, such that all G₁G₂G₃-free graphs contain a hamiltonian cycle. In [6], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁, G₂, G₃, none of which is a K 1 , s , s ≥ 3 such that G₁, G₂, G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In this paper, a characterization will be given of all triples G₁, G₂, G₃ with none being K 1 , 3 , such that all...

Independent cycles and paths in bipartite balanced graphs

Beata Orchel, A. Paweł Wojda (2008)

Discussiones Mathematicae Graph Theory

Similarity:

Bipartite graphs G = (L,R;E) and H = (L’,R’;E’) are bi-placeabe if there is a bijection f:L∪R→ L’∪R’ such that f(L) = L’ and f(u)f(v) ∉ E’ for every edge uv ∈ E. We prove that if G and H are two bipartite balanced graphs of order |G| = |H| = 2p ≥ 4 such that the sizes of G and H satisfy ||G|| ≤ 2p-3 and ||H|| ≤ 2p-2, and the maximum degree of H is at most 2, then G and H are bi-placeable, unless G and H is one of easily recognizable couples of graphs. This result implies easily that...

Unique factorization theorem

Peter Mihók (2000)

Discussiones Mathematicae Graph Theory

Similarity:

A property of graphs is any class of graphs closed under isomorphism. A property of graphs is induced-hereditary and additive if it is closed under taking induced subgraphs and disjoint unions of graphs, respectively. Let ₁,₂, ...,ₙ be properties of graphs. A graph G is (₁,₂,...,ₙ)-partitionable (G has property ₁ º₂ º... ºₙ) if the vertex set V(G) of G can be partitioned into n sets V₁,V₂,..., Vₙ such that the subgraph G [ V i ] of G induced by Vi belongs to i ; i = 1,2,...,n. A property is said...

Radio numbers for generalized prism graphs

Paul Martinez, Juan Ortiz, Maggy Tomova, Cindy Wyels (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A radio labeling is an assignment c:V(G) → N such that every distinct pair of vertices u,v satisfies the inequality d(u,v) + |c(u)-c(v)| ≥ diam(G) + 1. The span of a radio labeling is the maximum value. The radio number of G, rn(G), is the minimum span over all radio labelings of G. Generalized prism graphs, denoted Z n , s , s ≥ 1, n ≥ s, have vertex set (i,j) | i = 1,2 and j = 1,...,n and edge set ((i,j),(i,j ±1)) ∪ ((1,i),(2,i+σ)) | σ = -⌊(s-1)/2⌋...,0,...,⌊s/2⌋. In this paper we determine...

The hull number of strong product graphs

A.P. Santhakumaran, S.V. Ullas Chandran (2011)

Discussiones Mathematicae Graph Theory

Similarity:

For a connected graph G with at least two vertices and S a subset of vertices, the convex hull [ S ] G is the smallest convex set containing S. The hull number h(G) is the minimum cardinality among the subsets S of V(G) with [ S ] G = V ( G ) . Upper bound for the hull number of strong product G ⊠ H of two graphs G and H is obtainted. Improved upper bounds are obtained for some class of strong product graphs. Exact values for the hull number of some special classes of strong product graphs are obtained. Graphs...

The order of uniquely partitionable graphs

Izak Broere, Marietjie Frick, Peter Mihók (1997)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition V₁,...,Vₙ of V(G) such that, for each i = 1,...,n, the subgraph of G induced by V i has property i . If a graph G has a unique (₁,...,ₙ)-partition we say it is uniquely (₁,...,ₙ)-partitionable. We establish best lower bounds for the order of uniquely (₁,...,ₙ)-partitionable graphs, for various choices of ₁,...,ₙ.

Potential forbidden triples implying hamiltonicity: for sufficiently large graphs

Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson (2005)

Discussiones Mathematicae Graph Theory

Similarity:

In [1], Brousek characterizes all triples of connected graphs, G₁,G₂,G₃, with G i = K 1 , 3 for some i = 1,2, or 3, such that all G₁G₂ G₃-free graphs contain a hamiltonian cycle. In [8], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁,G₂,G₃, none of which is a K 1 , s , s ≥ 3 such that G₁G₂G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In [6], a characterization was given of all triples G₁,G₂,G₃ with none being K 1 , 3 , such that all G₁G₂G₃-free...

Reducible properties of graphs

P. Mihók, G. Semanišin (1995)

Discussiones Mathematicae Graph Theory

Similarity:

Let L be the set of all hereditary and additive properties of graphs. For P₁, P₂ ∈ L, the reducible property R = P₁∘P₂ is defined as follows: G ∈ R if and only if there is a partition V(G) = V₁∪ V₂ of the vertex set of G such that V G P and V G P . The aim of this paper is to investigate the structure of the reducible properties of graphs with emphasis on the uniqueness of the decomposition of a reducible property into irreducible ones.

Factorizations of properties of graphs

Izak Broere, Samuel John Teboho Moagi, Peter Mihók, Roman Vasky (1999)

Discussiones Mathematicae Graph Theory

Similarity:

A property of graphs is any isomorphism closed class of simple graphs. For given properties of graphs ₁,₂,...,ₙ a vertex (₁, ₂, ...,ₙ)-partition of a graph G is a partition V₁,V₂,...,Vₙ of V(G) such that for each i = 1,2,...,n the induced subgraph G [ V i ] has property i . The class of all graphs having a vertex (₁, ₂, ...,ₙ)-partition is denoted by ₁∘₂∘...∘ₙ. A property is said to be reducible with respect to a lattice of properties of graphs if there are n ≥ 2 properties ₁,₂,...,ₙ ∈ such that...

Structure of the set of all minimal total dominating functions of some classes of graphs

K. Reji Kumar, Gary MacGillivray (2010)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we study some of the structural properties of the set of all minimal total dominating functions ( T ) of cycles and paths and introduce the idea of function reducible graphs and function separable graphs. It is proved that a function reducible graph is a function separable graph. We shall also see how the idea of function reducibility is used to study the structure of T ( G ) for some classes of graphs.

Edge-connectivity of strong products of graphs

Bostjan Bresar, Simon Spacapan (2007)

Discussiones Mathematicae Graph Theory

Similarity:

The strong product G₁ ⊠ G₂ of graphs G₁ and G₂ is the graph with V(G₁)×V(G₂) as the vertex set, and two distinct vertices (x₁,x₂) and (y₁,y₂) are adjacent whenever for each i ∈ 1,2 either x i = y i or x i y i E ( G i ) . In this note we show that for two connected graphs G₁ and G₂ the edge-connectivity λ (G₁ ⊠ G₂) equals minδ(G₁ ⊠ G₂), λ(G₁)(|V(G₂)| + 2|E(G₂)|), λ(G₂)(|V(G₁)| + 2|E(G₁)|). In addition, we fully describe the structure of possible minimum edge cut sets in strong products of graphs.

On hereditary properties of composition graphs

Vadim E. Levit, Eugen Mandrescu (1998)

Discussiones Mathematicae Graph Theory

Similarity:

The composition graph of a family of n+1 disjoint graphs H i : 0 i n is the graph H obtained by substituting the n vertices of H₀ respectively by the graphs H₁,H₂,...,Hₙ. If H has some hereditary property P, then necessarily all its factors enjoy the same property. For some sort of graphs it is sufficient that all factors H i : 0 i n have a certain common P to endow H with this P. For instance, it is known that the composition graph of a family of perfect graphs is also a perfect graph (B. Bollobas, 1978),...

The structure and existence of 2-factors in iterated line graphs

Michael Ferrara, Ronald J. Gould, Stephen G. Hartke (2007)

Discussiones Mathematicae Graph Theory

Similarity:

We prove several results about the structure of 2-factors in iterated line graphs. Specifically, we give degree conditions on G that ensure L²(G) contains a 2-factor with every possible number of cycles, and we give a sufficient condition for the existence of a 2-factor in L²(G) with all cycle lengths specified. We also give a characterization of the graphs G where L k ( G ) contains a 2-factor.

Rotation and jump distances between graphs

Gary Chartrand, Heather Gavlas, Héctor Hevia, Mark A. Johnson (1997)

Discussiones Mathematicae Graph Theory

Similarity:

A graph H is obtained from a graph G by an edge rotation if G contains three distinct vertices u,v, and w such that uv ∈ E(G), uw ∉ E(G), and H = G-uv+uw. A graph H is obtained from a graph G by an edge jump if G contains four distinct vertices u,v,w, and x such that uv ∈ E(G), wx∉ E(G), and H = G-uv+wx. If a graph H is obtained from a graph G by a sequence of edge jumps, then G is said to be j-transformed into H. It is shown that for every two graphs G and H of the same order (at least...

Symmetries of embedded complete bipartite graphs

Erica Flapan, Nicole Lehle, Blake Mellor, Matt Pittluck, Xan Vongsathorn (2014)

Fundamenta Mathematicae

Similarity:

We characterize which automorphisms of an arbitrary complete bipartite graph K n , m can be induced by a homeomorphism of some embedding of the graph in S³.