Displaying similar documents to “Graphs with small additive stretch number”

Acyclic reducible bounds for outerplanar graphs

Mieczysław Borowiecki, Anna Fiedorowicz, Mariusz Hałuszczak (2009)

Discussiones Mathematicae Graph Theory

Similarity:

For a given graph G and a sequence ₁, ₂,..., ₙ of additive hereditary classes of graphs we define an acyclic (₁, ₂,...,Pₙ)-colouring of G as a partition (V₁, V₂,...,Vₙ) of the set V(G) of vertices which satisfies the following two conditions: 1. G [ V i ] i for i = 1,...,n, 2. for every pair i,j of distinct colours the subgraph induced in G by the set of edges uv such that u V i and v V j is acyclic. A class R = ₁ ⊙ ₂ ⊙ ... ⊙ ₙ is defined as the set of the graphs having an acyclic (₁, ₂,...,Pₙ)-colouring....

Criteria for of the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties

Izak Broere, Jozef Bucko, Peter Mihók (2002)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁,₂,...,ₙ be graph properties, a graph G is said to be uniquely (₁,₂, ...,ₙ)-partitionable if there is exactly one (unordered) partition V₁,V₂,...,Vₙ of V(G) such that G [ V i ] i for i = 1,2,...,n. We prove that for additive and induced-hereditary properties uniquely (₁,₂,...,ₙ)-partitionable graphs exist if and only if i and j are either coprime or equal irreducible properties of graphs for every i ≠ j, i,j ∈ 1,2,...,n.

4-cycle properties for characterizing rectagraphs and hypercubes

Khadra Bouanane, Abdelhafid Berrachedi (2017)

Czechoslovak Mathematical Journal

Similarity:

A ( 0 , 2 ) -graph is a connected graph, where each pair of vertices has either 0 or 2 common neighbours. These graphs constitute a subclass of ( 0 , λ ) -graphs introduced by Mulder in 1979. A rectagraph, well known in diagram geometry, is a triangle-free ( 0 , 2 ) -graph. ( 0 , 2 ) -graphs include hypercubes, folded cube graphs and some particular graphs such as icosahedral graph, Shrikhande graph, Klein graph, Gewirtz graph, etc. In this paper, we give some local properties of 4-cycles in ( 0 , λ ) -graphs and more specifically...

The decomposability of additive hereditary properties of graphs

Izak Broere, Michael J. Dorfling (2000)

Discussiones Mathematicae Graph Theory

Similarity:

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. If ₁,...,ₙ are properties of graphs, then a (₁,...,ₙ)-decomposition of a graph G is a partition E₁,...,Eₙ of E(G) such that G [ E i ] , the subgraph of G induced by E i , is in i , for i = 1,...,n. We define ₁ ⊕...⊕ ₙ as the property G ∈ : G has a (₁,...,ₙ)-decomposition. A property is said to be decomposable if there exist non-trivial hereditary properties ₁ and ₂ such...

A note on periodicity of the 2-distance operator

Bohdan Zelinka (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The paper solves one problem by E. Prisner concerning the 2-distance operator T₂. This is an operator on the class C f of all finite undirected graphs. If G is a graph from C f , then T₂(G) is the graph with the same vertex set as G in which two vertices are adjacent if and only if their distance in G is 2. E. Prisner asks whether the periodicity ≥ 3 is possible for T₂. In this paper an affirmative answer is given. A result concerning the periodicity 2 is added.

On characterization of uniquely 3-list colorable complete multipartite graphs

Yancai Zhao, Erfang Shan (2010)

Discussiones Mathematicae Graph Theory

Similarity:

For each vertex v of a graph G, if there exists a list of k colors, L(v), such that there is a unique proper coloring for G from this collection of lists, then G is called a uniquely k-list colorable graph. Ghebleh and Mahmoodian characterized uniquely 3-list colorable complete multipartite graphs except for nine graphs: K 2 , 2 , r r ∈ 4,5,6,7,8, K 2 , 3 , 4 , K 1 * 4 , 4 , K 1 * 4 , 5 , K 1 * 5 , 4 . Also, they conjectured that the nine graphs are not U3LC graphs. After that, except for K 2 , 2 , r r ∈ 4,5,6,7,8, the others have been proved not...

Paired domination in prisms of graphs

Christina M. Mynhardt, Mark Schurch (2011)

Discussiones Mathematicae Graph Theory

Similarity:

The paired domination number γ p r ( G ) of a graph G is the smallest cardinality of a dominating set S of G such that ⟨S⟩ has a perfect matching. The generalized prisms πG of G are the graphs obtained by joining the vertices of two disjoint copies of G by |V(G)| independent edges. We provide characterizations of the following three classes of graphs: γ p r ( π G ) = 2 γ p r ( G ) for all πG; γ p r ( K G ) = 2 γ p r ( G ) ; γ p r ( K G ) = γ p r ( G ) .

Histories in path graphs

Ludovít Niepel (2007)

Discussiones Mathematicae Graph Theory

Similarity:

For a given graph G and a positive integer r the r-path graph, P r ( G ) , has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length r-1, and their union forms either a cycle or a path of length k+1 in G. Let P r k ( G ) be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of P r k ( G ) . The k-history P r - k ( H ) is a subgraph of G that is induced by all edges that take part in the recursive...

On 𝓕-independence in graphs

Frank Göring, Jochen Harant, Dieter Rautenbach, Ingo Schiermeyer (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let be a set of graphs and for a graph G let α ( G ) and α * ( G ) denote the maximum order of an induced subgraph of G which does not contain a graph in as a subgraph and which does not contain a graph in as an induced subgraph, respectively. Lower bounds on α ( G ) and α * ( G ) are presented.

On the total k-domination number of graphs

Adel P. Kazemi (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let k be a positive integer and let G = (V,E) be a simple graph. The k-tuple domination number γ × k ( G ) of G is the minimum cardinality of a k-tuple dominating set S, a set that for every vertex v ∈ V, | N G [ v ] S | k . Also the total k-domination number γ × k , t ( G ) of G is the minimum cardinality of a total k -dominating set S, a set that for every vertex v ∈ V, | N G ( v ) S | k . The k-transversal number τₖ(H) of a hypergraph H is the minimum size of a subset S ⊆ V(H) such that |S ∩e | ≥ k for every edge e ∈ E(H). We know that for...

Roman bondage in graphs

Nader Jafari Rad, Lutz Volkmann (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A Roman dominating function on a graph G is a function f:V(G) → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of a Roman dominating function is the value f ( V ( G ) ) = u V ( G ) f ( u ) . The Roman domination number, γ R ( G ) , of G is the minimum weight of a Roman dominating function on G. In this paper, we define the Roman bondage b R ( G ) of a graph G with maximum degree at least two to be the minimum cardinality of all sets E’ ⊆ E(G)...

Nearly complete graphs decomposable into large induced matchings and their applications

Noga Alon, Ankur Moitra, Benjamin Sudakov (2013)

Journal of the European Mathematical Society

Similarity:

We describe two constructions of (very) dense graphs which are edge disjoint unions of large induced matchings. The first construction exhibits graphs on N vertices with ( N 2 ) - o ( N 2 ) edges, which can be decomposed into pairwise disjoint induced matchings, each of size N 1 - o ( 1 ) . The second construction provides a covering of all edges of the complete graph K N by two graphs, each being the edge disjoint union of at most N 2 - δ induced matchings, where δ > 0 , 076 . This disproves (in a strong form) a conjecture of Meshulam,...

The geodetic number of strong product graphs

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

Discussiones Mathematicae Graph Theory

Similarity:

For two vertices u and v of a connected graph G, the set I G [ u , v ] consists of all those vertices lying on u-v geodesics in G. Given a set S of vertices of G, the union of all sets I G [ u , v ] for u,v ∈ S is denoted by I G [ S ] . A set S ⊆ V(G) is a geodetic set if I G [ S ] = V ( G ) and the minimum cardinality of a geodetic set is its geodetic number g(G) of G. Bounds for the geodetic number of strong product graphs are obtainted and for several classes improved bounds and exact values are obtained.

Uniquely partitionable graphs

Jozef Bucko, Marietjie Frick, Peter Mihók, Roman Vasky (1997)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition of the vertex set V(G) into subsets V₁, ...,Vₙ such that the subgraph G [ V i ] induced by V i has property i ; i = 1,...,n. A graph G is said to be uniquely (₁, ...,ₙ)-partitionable if G has exactly one (₁,...,ₙ)-partition. A property is called hereditary if every subgraph of every graph with property also has property . If every graph that is a disjoint union of two graphs that have property also has property...

Remarks on D -integral complete multipartite graphs

Pavel Híc, Milan Pokorný (2016)

Czechoslovak Mathematical Journal

Similarity:

A graph is called distance integral (or D -integral) if all eigenvalues of its distance matrix are integers. In their study of D -integral complete multipartite graphs, Yang and Wang (2015) posed two questions on the existence of such graphs. We resolve these questions and present some further results on D -integral complete multipartite graphs. We give the first known distance integral complete multipartite graphs K p 1 , p 2 , p 3 with p 1 < p 2 < p 3 , and K p 1 , p 2 , p 3 , p 4 with p 1 < p 2 < p 3 < p 4 , as well as the infinite classes of distance integral...

On the minus domination number of graphs

Hailong Liu, Liang Sun (2004)

Czechoslovak Mathematical Journal

Similarity:

Let G = ( V , E ) be a simple graph. A 3 -valued function f V ( G ) { - 1 , 0 , 1 } is said to be a minus dominating function if for every vertex v V , f ( N [ v ] ) = u N [ v ] f ( u ) 1 , where N [ v ] is the closed neighborhood of v . The weight of a minus dominating function f on G is f ( V ) = v V f ( v ) . The minus domination number of a graph G , denoted by γ - ( G ) , equals the minimum weight of a minus dominating function on G . In this paper, the following two results are obtained. (1) If G is a bipartite graph of order n , then γ - ( G ) 4 n + 1 - 1 - n . (2) For any negative integer k and any positive integer...

Domination and independence subdivision numbers of graphs

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The domination subdivision number s d γ ( G ) of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of...

Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs

Éric Sopena (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The oriented chromatic number of an oriented graph G is the minimum order of an oriented graph H such that G admits a homomorphism to H . The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph U such that every orientation G of G admits a homomorphism to U . We give...