Contents ... Previous ... Next ... References
A Survey of Hereditary Properties of Graphs

5. Invariants Related to Hereditary Properties

In this section we are going to present a concept of (integer) monotone graph invariants and to show how they can be used to define some chains in the lattice (see Section 2), and compare known results corresponding to the invariants. On the other hand, such a comparison might lead to some new results and it would indicate open problems for specific invariants.

The concept of integer valued invariants can be extended to a more general concept of rational (or real) valued invariants.

Let be a given lattice and let P I. A non-negative integer valued function f : P , such that f(G)=f(H) for any two isomorphic graphs G,H P, is called the graph invariant (invariant, for short).

An invariant f on P in is called monotone if H G implies f(H) f(G), for any H,G P. If f(G H)= max{f(G), f(H)}, for any disjoint G and H, then f is called additive.

The first attempt to define an additive monotone graph invariant by similar conditions has been done by Frick [38].
Suppose that we have an invariant f : P . Let k0=min{f(G) : GP} and P0={G P : f(G)=k0}. Then in the lattice we have an interval [P0, P] and a chain

P0 P1 . . . Pk . . ., k ,
of properties in , defined in the following way
Pk={G P : f(G) k0+k}, for each k .

Note, that in the definition of P0 the inequality f(P) k0 is equivalent to the equality f(P)=k0. It is not difficult to observe, that for some invariants k0=0 and it leads us to already investigated properties O, W0, S0 and so on. Examples of all mentioned cases will be presented later on.

Conversely, let in the lattice a finite or countable chain

P0 P1 . . . Pk . . ., k0,
be given and let
P = Pk.
Then an invariant f : P by this chain is defined as follows:

f(G) = 0, if G P0 and
f(G) = k, if G Pk - Pk-1, for k 1.

From the above it follows that if HG, then f(H) f(G) and, if Pk (k0) are in a, then f(GH)= max{f(G),f(H)}, for any disjoint G and H.

Let an invariant f be defined by a chain as above and let Q P. Then we call an invariant g the restriction f to Q if g is defined by the chain

(*) P0 Q P1 Q P2 Q . . .,
which we call the restricted chain. In each case, for the chain (*) we can ask if the properties Pk Q, k 0, are non-empty or the equality between properties holds. In general, the answer on this question is not trivial.

Let the chain P0 P1, . . . Pn . . . in , be defined by an invariant f. A graph G Pk is called (Pk, ) -f critical if f(H)<f(G) for any HG and HG. It is clear that in the lattice , of all induced properties, a graph G is (Pk, )-f critical if f(G-v)<f(G), for any vertex v of G. We call such graphs (k,f)-critical, for short.

Similarly, in a graph G is (Pk, )-f critical if f(G-e)<f(G), for any edge e of G. We call such graphs, as usually, (k,f)-minimal.

5.1 Examples of Well-Known Graph Invariants

We will restrict our attention mainly to the lattices and , and assume P = I.

5.1.1 The Largest Order of Components of a Graph G: o(G)

This invariant defines the chain
O O1 O2 . . . .
Let ak= {P a : c(P)=k}, k0. (ak,e) is a sublattice of a with Ok as its least element.

5.1.2 The Clique Number: (G)

The clique number (G) of a graph G leads us to the chain
O = I0 I1 I2 . . .,
where Ik = {G I : (G)k+1 }.

The property Ik is the greatest element in ak.

5.1.3 The Chromatic Number: (G)

The chromatic number of a graph G defines the chain
O O2 O3 . . .,
where Ok= {G I : (G)k }, i.e., the class of all k-colourable graphs. Thus, k0=1 and P = I.

Restricted chains obtained from this one were intensively investigated. For example,

O O2 I1 O3 I1 . . .
or more generally,
O O2 Ik O3 Ik . . .
for k1. Non-emptiness of these properties follow from the well-known theorems of Zykov [105] or Mycielski [76].

If P = Tn, it is known, see [26], that in the chain

O O2 Tn O3 Tn . . .
the n+1 consecutive properties are non-empty (in the chain only proper subsets are considered), for n=1,2,3.

5.1.4 The Degeneracy: (G)

The degeneracy number (G) of a graph G is defined as follows: (G) = max{(H) : HG}. Let Dk={G I : (G)k}. Thus, we have the following chain
O = D0 D1 D2 . . . .

5.1.5 The Maximum Degree: (G)

Let Sk = {G I : (G)k}. We have the chain
O = S0 S1 S2 . . ..
All the above described properties satisfy in a, for k1, the following relations
Ok Sk Dk Ok+1 Ik,
each of them has completeness which equals to k. Only for k=1 we have O1= S1.

5.1.6 The Path Number: l(G)

For the invariant l(G), the length of the longest path, we get the following chain of hereditary properties:
O= W0 W1 W2 . . . .

5.1.7 The Size of a Graph G: e(G)

Let e(G)= |E(G)|. If we denote by k={G I : |E(G)|k}, then we have immediately the chain
O = 0 1 2 . . ..

5.2 Generalized Chromatic Number

Let P be a property of graphs. A P-partition (colouring) of a graph G is a partition (V1,. . . ,Vn) of V(G) such that the subgraph G[Vi] induced by the set Vi has the property P for each i=1,. . . ,n. If (V1, . . . ,Vn) is a P -partition of a graph G, then the corresponding vertex colouring c is defined by c(v)=i whenever vVi, for i=1,. . . ,n. The smallest integer n for which G has P-partition is called the P-chromatic (or P-vertex-partition) number of G and is denoted by P(G). The O-chromatic number is the ordinary chromatic number (see [17] for a survey and more details).

The P-chromatic number defines the chain

P P2 P3 . . .,
where Pk= {G I : P(G) i>k}.

5.3 The Choice Number

Let G be a graph and let L(v) be a list of colours (say, positive integers) prescribed for the vertex v, and P{}. A (P,L)-colouring is a graph P-colouring c(v) with the additional requirement that for all vV(G), c(v)L(v). If G admits a (P,L)-colouring, then G is said to be (P,L)-colourable. The graph G is (P,k)-choosable if it is (P,L)-colourable for every list~L of G satisfying |L(v)|=k for every vV(G). The P-choice number chP(G) is the smallest natural number k such that G is (P,k)-choosable. For more details see [13], where these concepts were introduced.

Vizing [100] and Erdős, Rubin and Taylor [36] independently introduce the idea of considering (O,L)-colouring and (O,k)-choosability (k-choosability, for short). In the both papers, the choosability version of Brooks' theorem [22] has been proved but the choosability version of Gallai's theorem [41] has been proved independently, by Thomassen [92] and by Kostochka et al. [60].

In [13] some extensions of these two basic theorems to (P,k)-choosability have been proved. If L(v) is the same for all vertices of G, these results generalize also the corresponding theorems of [17]. In [13] is proved that chP(G)- P(G) can be arbitrarily large in the following sense.

Theorem 62. Let Pa and 1c(P)<. Then for any nonnegative integer s there exists a graph Gs such that chP (Gs)-P(Gs)>s .

From the definition of (Pk, )-f critical graphs it follows that for a nontrivial property P, a graph G is (P,k)-choice critical if chP(G)=k 2 but chP(G-v)<k for all vertices v of G. Since in any (P,k)-choice critical graph G (see [13]) degG(v)(P)(k-1) for a degree of any vertex v of G, let us denote (the set of low vertices) by S(G)={v: v V(G), degG(v)=(P)(k-1)}.

Now we present a generalization of Gallai's and Brooks' theorems.

Theorem 63.([13]) Let P and G be a (k,P)-choice critical graph. Then any block B of G[S(G)] is one of the following types:

    {i} B is a complete graph,
    (ii)B is a (P)-regular graph belonging to C (P),
    (iii)BP\; and (B) (P),
    (iv)B is an odd cycle.

Theorem 64.([13]) Let Pa and G be a connected graph other than

    (i)a complete graph of order n(P)+1, n0,
    (ii)a (P)-regular graph belonging to C(P),
    (iii)an odd cycle if P=O.
Then

chP(G) .

Let CHk = {GI : chO(G) k}, i.e., it is the class of all k-choosable graphs. The completeness c(CHk)=k-1. Since any k-choosable graph is k-colourable, then by the result of [12], for P = O, we have Dk-1 CHk Ok.

In [17] similar results for generalized chromatic numbers P, are presented.

5.4 Invariants from Gallai Type Theorems

In 1959 Gallai presented his, now classical, theorem, involving the vertex covering number 0, the vertex independence number 0 , the edge covering number 1 and the edge independence number 1.

Theorem 65.([40]) For every nontrivial connected graph G with p vertices, we have

0 + 0 = p and 1 + 1 = p.

A large number of similar results and generalizations of this theorem have been obtained in subsequent years; they are called Gallai-Type Equalities. The typical Gallai-Type Equality has the form

f + g = p,
where f and g are integer (real) valued functions of some type defined on the class of (connected) graphs and p denotes the number of vertices in a graph.

For all parameters created from this type of theorem, the main problem is to find non-trivial relations with some other parameters and to characterize the maximal graphs with respect to ones. In this subsection examples of two such parameters and their generalizations will be presented.

5.4.1 The Vertex Covering Number

A set S of vertices of G is a vertex cover of G if each edge of G has at least one end vertex in set S. The cardinality of any smallest vertex cover is denoted by 0(G) and is called the vertex covering number of G. Let Bk={G I : 0(G)k}. By Gallai's Theorem, Bk.

5.4.2 Generalized Vertex Covering Number

Let P and G be a graph. A set SV(G) is P-independent in G if G[S] P. The maximum of the cardinalities of the maximal P-independent sets in G is called P-independence number of G and it is denoted by P(G). A subset of V(G) is called a vertex P-cover if it meets every non P-independent set of G. The minimum cardinality of a vertex P-cover is called vertex P-covering number and is denoted by P(G).
The following generalization of Gallai's Theorem has been proved in [53].

Theorem 66. For any P and a graph G of order p,

P(G) + P(G) = p.

Similarly, we have defined the chain of the following properties:

B k,P = {GI : P(G) k}.

5.4.3 Nieminen's Number or the Leafage Number

A nonempty subset D of the vertex set V of a graph G is a dominating set if every vertex in V-D is adjacent with a member of D. If uD and vV-D, and {u,v}E, we say that u dominates v and V is dominated by u.

The minimum of the cardinalities of the minimal dominating sets in G is called the domination number of G and it is denoted by (G).

The study of domination in graphs has been initiated by Ore [81], for a survey see the special volume of Discrete Mathematics86(1990).

Theorem 67.([79]) Let (G) be the domination number and (G) be the maximum number of pendant edges in a spanning forest of a graph G with p vertices. Then (G) + (G)=p.

We call (G) the leafage number of G.

5.4.4 Generalized Leafage Number

Let P and G=(V(G),E(G)) be a graph. Two vertices u and v of G are called P-adjacent if there is a subgraph H' of G isomorphic to HC(P) containing u and v. For a vertex vV by NP(v) we denote the P-neighbourhood of V, i.e., NP}(v)={uV : u is P-adjacent to v}. For a set XV, let NP(X)= vXNP(v). Especially, N(v)=NO(v).

Next, for a vertex vV(G) we denote the set of all forbidden subgraphs containing V by CG,P(v)={H'G: vV(H'), H'HC(P)}, where is an isomorphism relation.

The number |CG,P(v)| is called P-degree of V in G and it is denoted degG,P(v). If degG,P(v)=1, then V is said to be P-pendant. If degG,P(v)=0, then V is said to be P-isolated.

For a property P, let (P) = min{(H): HC(P)}.

A set DV(G) is said to be P-dominating in G if NP(v)D for any vV(G)-D.

A set DV(G) is said to be strongly P-dominating in G if for every vV(G)-D there is H'G containing v such that H'H C(P) and V(H')-{v}D.

The minimum of the cardinalities of the (strongly) P-dominating sets of G is called the (strong) P-domination number of G and is denoted by P(G) ('P(G)), respectively.

Notice, that if P=O, then P-dominating and strongly P-dominating sets in G are dominating sets in the ordinary sense.

Next, if P = In-2, then the In-2-dominating set in G is the Kn-dominating set in G (see [56]).

Let P and G be a graph. Let S be a spanning subgraph of G. A family XP(S) = {G1, G2,...,Gk} of induced subgraphs of S such that

    (1)GiH C(P) and
    (2)For any Gi there is a vertex viV(Gi) such that vi V(Gj), ji, 1i,jk is called a family of P-pendant subgraphs of S.

A vertex viV(Gi) satisfying (2) is called a P-pendant vertex in the family XP(S). The generalized leafage number P(G) of a graph G is the maximum number of P-pendant subgraphs in a spanning subgraph of the graph G.

Notice, that if P = O, then P(G)=(G).

Theorem 68.([16]) Let P. For every graph G of order p, we have

'P(G) + P(G) = p.

Hedetniemi and Laskar [54] proved a similar equality as in Nieminen's Theorem involving connectivity.

Generalization of the above result to an invariant involving connectivity and a property P in [16] is obtained. A survey of Gallai Type Equalities in [30] is presented.

5.5 Edge Partitions Invariants

A large class of invariants from an edge partition is derived. We will mention here only two well-known ones. In fact, the Ramsey Theory (see [46]) includes the most important results of this type.

In order to present the next results we need the following notation

P1 P2 = {G : E(G)=E1E2, G[Ei] Pi, i=1,2 }.

5.5.1 Chromatic Index: '

The chromatic index ' define the following chain of properties

O J1 . . . Jk . . .,
where Jk = {GI : '(G)k}, i.e., Jk = i=1k Pi, where Pi = O1, i=1,...,k.

A well-known theorem of Vizing [99] states that (G)'(G)(G) +1.

It easy to see that J1 = S1. But Sk Jk+1 Sk+1, for k2. On the other hand, the relation Sk O2 Jk seems to be very interesting.

The decision problem:

Is a graph G in Sk Jk, k3,
is NP-complete (see[43]).

5.5.2 Arboricity:

Let Ak = ki=1 Pi, where Pi = D1. The minimum k for which a graph G is in Ak is called the arboricity of G and is denoted by (G). The well-known result of Nash-Williams states that (G) = max{|E(H)|/(|V(H)|-1)}, where the maximum is taken over all induced subgraphs H of G with at least two vertices.

An example of a fine relation is (see [50]):

T3 I1 A2,
i.e., every planar triangle-free graph is the union of two forests.
1997