The hull number of strong product graphs

A.P. Santhakumaran; S.V. Ullas Chandran

Displaying similar documents to “The hull number of strong product 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} \in 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.

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

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

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

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

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 ₂ < \dots < 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...

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}] \in_{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 \in V_{i}$ and $v \in V_{j}$ is acyclic. A class R = ₁ ⊙ ₂ ⊙ ... ⊙ ₙ is defined as the set of the graphs having an acyclic (₁, ₂,...,Pₙ)-colouring....

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

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

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}] \in_{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.

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

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.

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

Maximal k-independent sets in graphs

Mostafa Blidia, Mustapha Chellali, Odile Favaron, Nacéra Meddah (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A subset of vertices of a graph G is k-independent if it induces in G a subgraph of maximum degree less than k. The minimum and maximum cardinalities of a maximal k-independent set are respectively denoted iₖ(G) and βₖ(G). We give some relations between βₖ(G) and $β_{j} (G)$ and between iₖ(G) and $i_{j} (G)$ for j ≠ k. We study two families of extremal graphs for the inequality i₂(G) ≤ i(G) + β(G). Finally we give an upper bound on i₂(G) and a lower bound when G is a cactus.

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

Radio k-labelings for Cartesian products of graphs

Mustapha Kchikech, Riadh Khennoufa, Olivier Togni (2008)

Discussiones Mathematicae Graph Theory

Similarity:

Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interfere. We study the problem of reducing interference by modeling this by a radio k-labeling problem on graphs: For a graph G and an integer k ≥ 1, a radio k-labeling of G is an assignment f of non negative integers to the vertices of G such that $| f (x) - f (y) | \geq k + 1 - d_{G} (x, y)$ , for any two vertices x and y, where $d_{G} (x, y)$ is the distance between x and y in G. The radio k-chromatic...

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

Power Domination in Knödel Graphs and Hanoi Graphs

Seethu Varghese, A. Vijayakumar, Andreas M. Hinz (2018)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we study the power domination problem in Knödel graphs WΔ,2ν and Hanoi graphs [...] Hpn $H_{p}^{n}$ . We determine the power domination number of W3,2ν and provide an upper bound for the power domination number of Wr+1,2r+1 for r ≥ 3. We also compute the k-power domination number and the k-propagation radius of [...] Hp2 $H_{p}^{2}$ .

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.

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

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} \in P ₁$ and $⟨ V ₂ ⟩_{G} \in 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.

On 2-periodic graphs of a certain graph operator

Ivan Havel, Bohdan Zelinka (2001)

Discussiones Mathematicae Graph Theory

Similarity:

We deal with the graph operator $\bar{P o w ₂}$ defined to be the complement of the square of a graph: $\bar{P o w ₂} (G) = \bar{P o w ₂ (G)}$ . Motivated by one of many open problems formulated in [6] we look for graphs that are 2-periodic with respect to this operator. We describe a class of bipartite graphs possessing the above mentioned property and prove that for any m,n ≥ 6, the complete bipartite graph $K_{m, n}$ can be decomposed in two edge-disjoint factors from . We further show that all the incidence graphs of Desarguesian finite projective...