Difference labelling of cacti

Martin Sonntag

Displaying similar documents to “Difference labelling of cacti”

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

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

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

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.

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

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) \to {- 1, 0, 1}$ is said to be a minus dominating function if for every vertex $v \in V$ , $f (N [v]) = \sum_{u \in N [v]} f (u) \geq 1$ , where $N [v]$ is the closed neighborhood of $v$ . The weight of a minus dominating function $f$ on $G$ is $f (V) = \sum_{v \in 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) \geq 4 (\sqrt{n + 1} - 1) - n .$ (2) For any negative integer $k$ and any positive integer...

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

Restrained domination in unicyclic graphs

Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas van der Merwe (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by $γ_{r} (G)$ , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then $γ_{r} (U) \geq ⎡ n / 3 ⎤$ , and provide a characterization of graphs achieving this bound.

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.

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

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

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

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

Variations on a sufficient condition for Hamiltonian graphs

Ahmed Ainouche, Serge Lapiquonne (2007)

Discussiones Mathematicae Graph Theory

Similarity:

Given a 2-connected graph G on n vertices, let G* be its partially square graph, obtained by adding edges uv whenever the vertices u,v have a common neighbor x satisfying the condition $N_{G} (x) \subseteq N_{G} [u] \cup N_{G} [v]$ , where $N_{G} [x] = N_{G} (x) \cup x$ . In particular, this condition is satisfied if x does not center a claw (an induced $K_{1, 3}$ ). Clearly G ⊆ G* ⊆ G², where G² is the square of G. For any independent triple X = x,y,z we define σ̅(X) = d(x) + d(y) + d(z) - |N(x) ∩ N(y) ∩ N(z)|. Flandrin et al. proved that a 2-connected graph G is hamiltonian...

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

Graphs with small additive stretch number

Dieter Rautenbach (2004)

Discussiones Mathematicae Graph Theory

Similarity:

The additive stretch number $s_{a d d} (G)$ of a graph G is the maximum difference of the lengths of a longest induced path and a shortest induced path between two vertices of G that lie in the same component of G.We prove some properties of minimal forbidden configurations for the induced-hereditary classes of graphs G with $s_{a d d} (G) \leq k$ for some k ∈ N₀ = 0,1,2,.... Furthermore, we derive characterizations of these classes for k = 1 and k = 2.

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

Iterated neighborhood graphs

Martin Sonntag, Hanns-Martin Teichert (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph $(V, E_{N})$ where $E_{N}$ = a,b | a ≠ b, x,a ∈ E and x,b ∈ E for some x ∈ V. It is well-known that the neighborhood graph N(G) is connected if and only if the graph G is connected and non-bipartite. We present some results concerning the k-iterated neighborhood graph $N^{k} (G) : = N (N (. . . N (G)))$ of G. In particular we investigate conditions for G and k such that $N^{k} (G)$ becomes a complete graph.