Displaying similar documents to “Asymptotical estimation of some characteristics of finite 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. ...

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

Control flow graphs and code coverage

Robert Gold (2010)

International Journal of Applied Mathematics and Computer Science

Similarity:

The control flow of programs can be represented by directed graphs. In this paper we provide a uniform and detailed formal basis for control flow graphs combining known definitions and results with new aspects. Two graph reductions are defined using only syntactical information about the graphs, but no semantical information about the represented programs. We prove some properties of reduced graphs and also about the paths in reduced graphs. Based on graphs, we define statement coverage...