(H,k) stable graphs with minimum size

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

The search session has expired. Please query the service again.

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.