(H,k) stable graphs with minimum size

Aneta Dudek; Artur Szymański; Małgorzata Zwonek

Displaying similar documents to “(H,k) stable graphs with minimum size”

(H,k) stable bipartite graphs with minimum size

Aneta Dudek, Małgorzata Zwonek (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let us call a graph G(H;k) vertex stable if it contains a subgraph H after removing any of its k vertices. In this paper we are interested in finding the $(K_{n, n + 1}; 1)$ (respectively $(K_{n, n}; 1)$ ) vertex stable graphs with minimum size.

On the stability for pancyclicity

Ingo Schiermeyer (2001)

Discussiones Mathematicae Graph Theory

Similarity:

A property P defined on all graphs of order n is said to be k-stable if for any graph of order n that does not satisfy P, the fact that uv is not an edge of G and that G + uv satisfies P implies $d_{G} (u) + d_{G} (v) < k$ . Every property is (2n-3)-stable and every k-stable property is (k+1)-stable. We denote by s(P) the smallest integer k such that P is k-stable and call it the stability of P. This number usually depends on n and is at most 2n-3. A graph of order n is said to be pancyclic if it contains cycles...

Stable sets for $(P ₆, K_{2, 3})$ -free graphs

Raffaele Mosca (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The Maximum Stable Set (MS) problem is a well known NP-hard problem. However different graph classes for which MS can be efficiently solved have been detected and the augmenting graph technique seems to be a fruitful tool to this aim. In this paper we apply a recent characterization of minimal augmenting graphs [22] to prove that MS can be solved for $(P ₆, K_{2, 3})$ -free graphs in polynomial time, extending some known results.

On Minimum (Kq, K) Stable Graphs

J.L. Fouquet, H. Thuillier, J.M. Vanherpe, A.P. Wojda (2013)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is a (Kq, k) stable graph (q ≥ 3) if it contains a Kq after deleting any subset of k vertices (k ≥ 0). Andrzej ˙ Zak in the paper On (Kq; k)-stable graphs, ( doi:/10.1002/jgt.21705) has proved a conjecture of Dudek, Szyma´nski and Zwonek stating that for sufficiently large k the number of edges of a minimum (Kq, k) stable graph is (2q − 3)(k + 1) and that such a graph is isomorphic to sK2q−2 + tK2q−3 where s and t are integers such that s(q − 1) + t(q − 2) − 1 = k. We have...

On well-covered graphs of odd girth 7 or greater

Bert Randerath, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Similarity:

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth...

k-independence stable graphs upon edge removal

Mustapha Chellali, Teresa W. Haynes, Lutz Volkmann (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Let k be a positive integer and G = (V(G),E(G)) a graph. A subset S of V(G) is a k-independent set of G if the subgraph induced by the vertices of S has maximum degree at most k-1. The maximum cardinality of a k-independent set of G is the k-independence number βₖ(G). A graph G is called β¯ₖ-stable if βₖ(G-e) = βₖ(G) for every edge e of E(G). First we give a necessary and sufficient condition for β¯ₖ-stable graphs. Then we establish four equivalent conditions for β¯ₖ-stable trees. ...

Square-stable and well-covered graphs.

Levit, Vadim E., Mândrescu, Eugen (2005)

Acta Universitatis Apulensis. Mathematics - Informatics

Similarity:

On integral sum graphs with a saturated vertex

Zhibo Chen (2010)

Czechoslovak Mathematical Journal

Similarity:

As introduced by F. Harary in 1994, a graph $G$ is said to be an $i n t e g r a l$ $s u m$ $g r a p h$ if its vertices can be given a labeling $f$ with distinct integers so that for any two distinct vertices $u$ and $v$ of $G$ , $u v$ is an edge of $G$ if and only if $f (u) + f (v) = f (w)$ for some vertex $w$ in $G$ . We prove that every integral sum graph with a saturated vertex, except the complete graph $K_{3}$ , has edge-chromatic number equal to its maximum degree. (A vertex of a graph $G$ is said to be if it is adjacent to every...

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

Cores and shells of graphs

Allan Bickle (2013)

Mathematica Bohemica

Similarity:

The $k$ -core of a graph $G$ , $C_{k} (G)$ , is the maximal induced subgraph $H \subseteq G$ such that $δ (G) \geq k$ , if it exists. For $k > 0$ , the $k$ -shell of a graph $G$ is the subgraph of $G$ induced by the edges contained in the $k$ -core and not contained in the $(k + 1)$ -core. The core number of a vertex is the largest value for $k$ such that $v \in C_{k} (G)$ , and the maximum core number of a graph, $\hat{C} (G)$ , is the maximum of the core numbers of the vertices of $G$ . A graph $G$ is $k$ -monocore if $\hat{C} (G) = δ (G) = k$ . This paper discusses some basic results on the structure of $k$ -cores and...

Digraphs with isomorphic underlying and domination graphs: connected $U G^{c} (d)$

Kim A.S. Factor, Larry J. Langley (2007)

Discussiones Mathematicae Graph Theory

Similarity:

The domination graph of a directed graph has an edge between vertices x and y provided either (x,z) or (y,z) is an arc for every vertex z distinct from x and y. We consider directed graphs D for which the domination graph of D is isomorphic to the underlying graph of D. We demonstrate that the complement of the underlying graph must have k connected components isomorphic to complete graphs, paths, or cycles. A complete characterization of directed graphs where k = 1 is presented. ...

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.

Join of two graphs admits a nowhere-zero $3$ -flow

Saieed Akbari, Maryam Aliakbarpour, Naryam Ghanbari, Emisa Nategh, Hossein Shahmohamad (2014)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a graph, and $λ$ the smallest integer for which $G$ has a nowhere-zero $λ$ -flow, i.e., an integer $λ$ for which $G$ admits a nowhere-zero $λ$ -flow, but it does not admit a $(λ - 1)$ -flow. We denote the minimum flow number of $G$ by $Λ (G)$ . In this paper we show that if $G$ and $H$ are two arbitrary graphs and $G$ has no isolated vertex, then $Λ (G \lor H) \leq 3$ except two cases: (i) One of the graphs $G$ and $H$ is $K_{2}$ and the other is $1$ -regular. (ii) $H = K_{1}$ and $G$ is a graph with at least one isolated vertex or a component whose every...