Displaying similar documents to “Edge-connectivity of strong products of graphs”

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

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

Graceful signed graphs

Mukti Acharya, Tarkeshwar Singh (2004)

Czechoslovak Mathematical Journal

Similarity:

A ( p , q ) -sigraph S is an ordered pair ( G , s ) where G = ( V , E ) is a ( p , q ) -graph and s is a function which assigns to each edge of G a positive or a negative sign. Let the sets E + and E - consist of m positive and n negative edges of G , respectively, where m + n = q . Given positive integers k and d , S is said to be ( k , d ) -graceful if the vertices of G can be labeled with distinct integers from the set { 0 , 1 , , k + ( q - 1 ) d } such that when each edge u v of G is assigned the product of its sign and the absolute difference of the integers assigned to...

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

New edge neighborhood graphs

Ali A. Ali, Salar Y. Alsardary (1997)

Czechoslovak Mathematical Journal

Similarity:

Let G be an undirected simple connected graph, and e = u v be an edge of G . Let N G ( e ) be the subgraph of G induced by the set of all vertices of G which are not incident to e but are adjacent to u or v . Let 𝒩 e be the class of all graphs H such that, for some graph G , N G ( e ) H for every edge e of G . Zelinka [3] studied edge neighborhood graphs and obtained some special graphs in 𝒩 e . Balasubramanian and Alsardary [1] obtained some other graphs in 𝒩 e . In this paper we given some new graphs in 𝒩 e .

On generalized shift graphs

Christian Avart, Tomasz Łuczak, Vojtěch Rödl (2014)

Fundamenta Mathematicae

Similarity:

In 1968 Erdős and Hajnal introduced shift graphs as graphs whose vertices are the k-element subsets of [n] = 1,...,n (or of an infinite cardinal κ ) and with two k-sets A = a , . . . , a k and B = b , . . . , b k joined if a < a = b < a = b < < a k = b k - 1 < b k . They determined the chromatic number of these graphs. In this paper we extend this definition and study the chromatic number of graphs defined similarly for other types of mutual position with respect to the underlying ordering. As a consequence of our result, we show the existence of a graph with...

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

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

2-halvable complete 4-partite graphs

Dalibor Fronček (1998)

Discussiones Mathematicae Graph Theory

Similarity:

A complete 4-partite graph K m , m , m , m is called d-halvable if it can be decomposed into two isomorphic factors of diameter d. In the class of graphs K m , m , m , m with at most one odd part all d-halvable graphs are known. In the class of biregular graphs K m , m , m , m with four odd parts (i.e., the graphs K m , m , m , n and K m , m , n , n ) all d-halvable graphs are known as well, except for the graphs K m , m , n , n when d = 2 and n ≠ m. We prove that such graphs are 2-halvable iff n,m ≥ 3. We also determine a new class of non-halvable graphs K m , m , m , m with three...

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

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

Centers of n-fold tensor products of graphs

Sarah Bendall, Richard Hammack (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Formulas for vertex eccentricity and radius for the n-fold tensor product G = i = 1 G i of n arbitrary simple graphs G i are derived. The center of G is characterized as the union of n+1 vertex sets of form V₁×V₂×...×Vₙ, with V i V ( G i ) .

Graph domination in distance two

Gábor Bacsó, Attila Tálos, Zsolt Tuza (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class of graphs, Domₖ is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ which is also connected. In our notation, Dom coincides with Dom₁. In this paper we prove that D o m D o m u = D o m u holds for u = all connected graphs without induced P u (u ≥ 2). (In particular,...

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

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.