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

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

Displaying similar documents to “On Minimum (Kq, K) Stable Graphs”

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

(H,k) stable graphs with minimum size

Aneta Dudek, Artur Szymański, Małgorzata Zwonek (2008)

Discussiones Mathematicae Graph Theory

Similarity:

Let us call a G (H,k) graph vertex stable if it contains a subgraph H ever after removing any of its k vertices. By Q(H,k) we will denote the minimum size of an (H,k) vertex stable graph. In this paper, we are interested in finding Q(₃,k), Q(₄,k), Q ( K 1 , p , k ) and Q(Kₛ,k).

A Note on the Uniqueness of Stable Marriage Matching

Ewa Drgas-Burchardt (2013)

Discussiones Mathematicae Graph Theory

Similarity:

In this note we present some sufficient conditions for the uniqueness of a stable matching in the Gale-Shapley marriage classical model of even size. We also state the result on the existence of exactly two stable matchings in the marriage problem of odd size with the same conditions.

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

On The Roman Domination Stable Graphs

Majid Hajian, Nader Jafari Rad (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A Roman dominating function (or just RDF) on a graph G = (V,E) is a function f : V → {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF f is the value f(V (G)) = Pu2V (G) f(u). The Roman domination number of a graph G, denoted by R(G), is the minimum weight of a Roman dominating function on G. A graph G is Roman domination stable if the Roman domination number of G remains unchanged under...

On the Number ofα-Labeled Graphs

Christian Barrientos, Sarah Minion (2018)

Discussiones Mathematicae Graph Theory

Similarity:

When a graceful labeling of a bipartite graph places the smaller labels in one of the stable sets of the graph, it becomes an α-labeling. This is the most restrictive type of difference-vertex labeling and it is located at the very core of this research area. Here we use an extension of the adjacency matrix to count and classify α-labeled graphs according to their size, order, and boundary value.

Around stable forking

Byunghan Kim, A. Pillay (2001)

Fundamenta Mathematicae

Similarity:

We discuss various conjectures and problems around the issue of when and whether stable formulas are responsible for forking in simple theories. We prove that if the simple theory T has strong stable forking then any complete type is a nonforking extension of a complete type which is axiomatized by instances of stable formulas. We also give another treatment of the first author's result which identifies canonical bases in supersimple theories.

Stable graphs

Klaus-Peter Podewski, Martin Ziegler (1978)

Fundamenta Mathematicae

Similarity:

Superstable graphs

Heinrich Herre, Allan Mekler, Kenneth Smith (1983)

Fundamenta Mathematicae

Similarity:

Decompositions of saturated models of stable theories

M. C. Laskowski, S. Shelah (2006)

Fundamenta Mathematicae

Similarity:

We characterize the stable theories T for which the saturated models of T admit decompositions. In particular, we show that countable, shallow, stable theories with NDOP have this property.