Operations Research
Report 2014-03
Bounds on the stability number of a
graph via the inverse theta function
Miklós Ujvári
June 2014
c 2014 Department of Operations Research,
Copyright Eötvös Loránd University of Sciences,
Budapest, Hungary
Eötvös Loránd University of Sciences
Department of Operations Research
http://www.cs.elte.hu/opres/orr/
ISSN 1215 - 5918
3
Operations Research Reports No. 2014-03
Bounds on the stability number of a
graph via the inverse theta function
where I is the identity matrix, and J denotes the matrix with all elements
equal to one. The disjoint union of the graphs G1 and G2 is the graph G1 +G2
with adjacency matrix
A(G1 )
0
A(G1 + G2 ) :=
.
0
A(G2 )
µG = n − 1 − µG , µG1 +G2 =
Abstract
In the paper we consider degree, spectral, and semidefinite bounds
on the stability number of a graph. The bounds are obtained via reformulations and variants of the inverse theta function, a notion recently
introduced by the author in a previous work.
Keywords: stability number, inverse theta number.
Introduction
In this paper we provide several new descriptions and variants of the inverse
theta function, a notion recently introduced by the author (see [10]). We also
present some applications in the stable set problem, bounds on the cardinality
of a maximum stable set in a graph.
We start the paper with describing sandwich theorems on the inverse theta
number and its predecessor, the theta number (see [3]). First we fix some
notation. Let n ∈ N , and let G = (V (G), E(G)) be an undirected graph,
with vertex set V (G) = {1, . . . , n}, and with edge set E(G) ⊆ {{i, j} : i 6= j}.
Let A(G) be the 0-1 adjacency matrix of the graph G, that is let
A(G) := (aij ) ∈ {0, 1}n×n, where aij :=
Miklós Ujvári
Let (δ1 , . . . , δn ) be the sum of the row vectors of the adjacency matrix
A(G). The elements of this vector are the degrees of the vertices of the graph
G. We define similarly the values δ 1 , . . . , δ n in the complementary graph G
instead of G. Let ∆G (resp. µG ) be the maximum (resp. the arithmetic mean)
of the degrees in the graph G. Note that
Miklós Ujvári
1
4
0, if {i, j} 6∈ E(G),
1, if {i, j} ∈ E(G).
The complementary graph G is the graph with adjacency matrix
A(G) := J − I − A(G),
2014-06-30
n 1 µG 1 + n 2 µG 2
.
n1 + n2
(1)
By Rayleigh’s theorem (see [6]) for a symmetric matrix M = M T ∈ Rn×n
the minimum and maximum eigenvalue, λM resp. ΛM , can be expressed as
λM = min uT M u, ΛM = max uT M u.
||u||=1
||u||=1
By the Perron-Frobenius theorem (see [5]) for an elementwise nonnegative
n×n
symmetric matrix M = M T ∈ R+
the maximum is attained for a nonnegative unit (eigen)vector: we have ΛM = uT M u for some u ∈ Rn+ , uT u = 1.
n×n
Furthermore, if M = M T ∈ R+
, then −λM ≤ ΛM .
The maximum (resp. minimum) eigenvalue of the adjacency matrix A(G)
is denoted by ΛG (resp. λG ). By Exercise 11.14 in [4], we have
p
p
µG , ∆G ≤ ΛG ≤ ∆G , µG (n − 1).
(2)
The set of the n by n real symmetric positive semidefinite matrices will be
n
denoted by S+
, that is
n
S+
:= M ∈ Rn×n : M = M T , uT M u ≥ 0 (u ∈ Rn ) .
For example, the Laplacian matrix of the graph G,
n
.
L(G) := Dδ1 ,...,δn − A(G) ∈ S+
(Here Dδ1 ,...,δn denotes the diagonal matrix with diagonal elements δ1 , . . . , δn .)
It is well-known (see [6]), that the following statements are equivalent for
n
a symmetric matrix M = (mij ) ∈ Rn×n : a) M ∈ S+
; b) λM ≥ 0; c) M is
Operations Research Reports No. 2014-03
Bounds on the stability number of a graph via the inverse theta function
5
Gram matrix, that is mij = viT vj (i, j = 1, . . . , n) for some vectors v1 , . . . , vn .
n
Furthermore, by Lemma 2.1 in [8], the set S+
can be described as
!n
T
m
a
a
m
∈
N
,
a
∈
R
(1
≤
i
≤
n)
j
i
i
n
T
−
1
. (3)
S+
=
a ai = 1 (1 ≤ i ≤ n)
(ai aTj )11
i
i,j=1
The stability number, α(G), is the maximum cardinality of the (so-called
stable) sets S ⊆ V (G) such that {i, j} ⊆ S implies {i, j} 6∈ E(G). The
chromatic number, χ(G), is the minimum number of stable sets covering the
vertex set V (G).
Let us define an orthonormal representation of the graph G (shortly, o.r.
of G) as a system of vectors a1 , . . . , an ∈ Rm for some m ∈ N , satisfying
6
Analogously, the inverse theta number, ι(G), satisfies the inverse sandwich
inequality,
(α(G))2 + n − α(G) ≤ ι(G) ≤ nϑ(G),
(6)
see [10]. Here the inverse theta number, defined as
( n
)
X
1
ι(G) := inf
: a1 , . . . , an o.r. of G ,
(ai aTi )11
i=1
equals the common attained optimal value of the primal-dual semidefinite
programs
(T P − )
(T D− )
aTi ai = 1 (i = 1, . . . , n), aTi aj = 0 ({i, j} ∈ E(G)).
In the seminal paper [3] L. Lovász proved the following result, now popularly called sandwich theorem, see [1]:
Miklós Ujvári
n
,
inf tr (Z) + n, zij = −1 ({i, j} ∈ E(G)), Z = (zij ) ∈ S+
m
=
1
(i
=
1,
.
.
.
,
n),
ii
mij = 0 ({i, j} ∈ E(G)),
sup tr (JM ),
n
.
M = (mij ) ∈ S+
where ϑ(G) is the Lovász number of the graph G, defined as
1
ϑ(G) := inf max
:
a
,
.
.
.
,
a
o.r.
of
G
.
1
n
1≤i≤n (ai aT
i )11
Moreover, rewriting the feasible solution M of the program (T D− ) as the
Gram matrix M = (bTi bj ) for some vectors b1 , . . . , bn ∈ Rm , we obtain the
following analogue of (5):
n
X
bTi bj : b1 , . . . , bn o.r. of G .
ι(G) = max
(7)
The Lovász number has several equivalent descriptions, see [3]. For example, by (3) and standard semidefinite duality theory (see e.g. [7]), it is the
common optimal value of the Slater-regular primal-dual semidefinite programs
xii = λ − 1 (i ∈ V (G)),
(T P )
min λ,
x = −1 ({i, j} ∈ E(G)),
ij
n
X = (xij ) ∈ S+
,λ∈R
2
α(G) ≤ ϑ(G) ≤ χ(G),
and
(T D)
tr (Y ) = 1,
max tr (JY ),
yij = 0 ({i, j} ∈ E(G)),
n
Y = (yij ) ∈ S+
.
(4)
(Here tr stands for trace.) Reformulating the program (T D), Lovász derived
the following dual description of the theta number (Theorem 5 in [3]):
( n
)
X
T
(bi bi )11 : b1 , . . . , bn o.r. of G .
ϑ(G) = max
(5)
i=1
Operations Research Reports No. 2014-03
i,j=1
The structure of the paper is as follows: In Section 2 we will describe a
refinement of (7) and also several new descriptions of the inverse theta function
(with well-known analogues in the theory of the theta function). Some of these
results will be applied in Section 3, where we present two new lower bounds
for the stability number of a graph, and examine their additivity properties.
Finally, in Section 4 we study two variants of the inverse theta function, and
derive further bounds in the stable set problem.
New descriptions of ι(G)
In this section we will describe three reformulations of the inverse theta number of a graph G. The results have analogues in the theory of the theta
function, which we will mention in chronological order.
Let us denote by AG the following set of matrices:
aii = 0 (i = 1, . . . , n),
AG := A = (aij ) ∈ Rn×n aij = 0 ({i, j} ∈ E(G)),
.
aij = aji ({i, j} ∈ E(G))
Operations Research Reports No. 2014-03
Bounds on the stability number of a graph via the inverse theta function
7
We will describe bounds for the minimum eigenvalue λA with A ∈ AG .
First, we have for A ∈ AG the lower bounds
λA ≥ λ|A| ≥ −Λ|A| ≥ −ΛG · max |aij |,
8
Miklós Ujvári
hold. Hence, the two programs have the same (attained) optimal value. A different approach leads to another description of the inverse theta number.
i,j
by Rayleigh’s theorem and the Perron-Frobenius theorem. (Here |A| ∈ Rn×n
denotes the elementwise maximum of the matrices A and (0).)
On the other hand, using an equivalent form of the reformulation
mii = 1 (i = 1, . . . , n),
ϑ(G) = max ΛM mij = 0 ({i, j} ∈ E(G)),
,
n
M = (mij ) ∈ S+
(see for example [1], [10]), L. Lovász proved in Theorem 6 of [3] the upper
bound
ΛA
(A ∈ AG ).
(8)
λA ≤
1 − ϑ(G)
Analogously, as a consequence of the next theorem, we have also the upper
bound
tr (JA)
(A ∈ AG ).
(9)
λA ≤
n − ι(G)
(Note that by Rayleigh’s theorem tr (JA) ≤ nΛA , and by the inverse sandwich
theorem ι(G) − n ≤ n(ϑ(G) − 1) so there is no obvious dominance relation
between the bounds in (8) and (9).)
THEOREM 2.1The program
(P1 ) :
sup n +
tr (JA)
, A ∈ AG
−λA
has attained optimal value ι(G).
Proof. The variable transformations
MA := I +
1
A, AM := M − I
−λA
show that programs (T D− ) and (P1 ) are equivalent: if A and M are feasible
solutions of (P1 ) and (T D− ), respectively, then MA and AM are feasible
solutions of the other program such that between the corresponding values
the inequalities
tr (JMA ) ≥ n +
tr (JAM )
tr (JA)
, n+
≥ tr (JM )
−λA
−λAM
Operations Research Reports No. 2014-03
Karger, Motwani, and Sudan proved the reformulation
nii = 1 (i = 1, . . . , n),
1
,
= min ν nij = ν ({i, j} ∈ E(G)),
1 − ϑ(G)
n
N = (nij ) ∈ S+
,ν∈R
and used a variant of this theorem in their graph colouring algorithm. (See
[2] for a summary of related results.) By the inverse sandwich theorem we
have the lower bound
n
1
≥
;
(10)
1 − ϑ(G)
n − ι(G)
we will show that this latter value can be obtained as the optimal value of a
semidefinite program, too.
Let us consider the primal-dual semidefinite programs
b11 − bii = 0 (i = 2, . . . , n),
bij = 0 ({i, j} ∈ E(G)),
(P2 ) :
sup −tr B,
n
tr ((J − I)B) = 1, B = (bij ) ∈ S+
,
tr C = n,
(D2 ) :
inf γ,
c = γ ({i, j} ∈ E(G)),
ij
n
C = (cij ) ∈ S+
,γ∈R
(see also Theorem 4.1 for a variant). The programs have common attained
optimal value by standard semidefinite duality theory, see for example [7].
THEOREM 2.2The programs (P2 ) and (D2 ) have (common attained) optimal value n/(n − ι(G)).
Proof. Similarly as in the proof of Theorem 2.1, the variable transformations
MB :=
n
1
B, BM :=
M
tr B
tr (JM ) − n
show the equivalence of programs (P2 ) and n/(n − (T D− )), where the latter
program can be obtained from (T D− ) formally exchanging its value function
tr (JM ) for n/(n − tr (JM )) and adding the extra constraint tr (JM ) > n. Now, we turn to the third description of the inverse theta number.
Operations Research Reports No. 2014-03
Bounds on the stability number of a graph via the inverse theta function
9
We will use the following lemma, a slight modification of (7).
LEMMA 2.1For any graph G,
n
X
ˆ
ˆ
b
,
.
.
.
,
b
o.r.
of
G
1
n
ˆbT ˆbj ι(G) = sup
,
i
T
e1 ˆbi > 0 for i = 1, . . . , n
i,j=1
with e1 denoting the m-vector (1, 0, . . . , 0)T .
Proof. Let (bi ) be an orthonormal representation of G such that
ι(G) =
n
X
bTi bj
i,j=1
(that is an optimal solution in (7)). For 0 < ε < 1, let us define an orthonormal
representation (ˆbi (ε)) of G the following way:
√
1 − ε2 · O
(ˆbi (ε)) :=
,
εb1 , . . . , εbn
where O ∈ Rn×n is an orthogonal matrix satisfying eT1 O > 0. Note that then
eT1 ˆbi (ε) > 0 holds for all i. On the other hand, it can easily be verified that
n
X
i,j=1
ˆbT (ε)ˆbj (ε) → ι(G) (ε → 1).
i
Hence, we have proved
n
X
ˆ
ˆ
ˆbT ˆbj b1 , . . . , bn o.r. of G
ι(G) ≤ sup
i
eT ˆb > 0 for i = 1, . . . , n ,
1 i
i,j=1
which is the nontrivial part of the lemma. 10
3
equals ι(G). Lower bounds on α(G)
In this section we will describe two lower bounds on the stability number of
a graph G, and examine their additivity properties.
Note that the
Z1 := L(G), Z2 := ΛG I − A(G)
feasible solutions in (T P − ) give the inequalities
q
q
p
ι(G) ≤ n(µG + 1), n(ΛG + 1).
By Exercises 11.20 and 11.14 in [4], we have
p
χ(G) ≤ ΛG + 1 ≤ µG (n − 1) + 1, µG ≤ ΛG .
On the other hand, easy calculation verifies
p
p
µG (n − 1) + 1 ≤ n(µG + 1).
Hence, we have
q
q
n(µG + 1) ≤ n(ΛG + 1).
p
On the dual side instead of ι(G), χ(G) we can approximate ι(G)/n, α(G).
Note that
D1 := L(G), D2 := ΛG I − A(G)
χ(G) ≤
are feasible solutions of the program (P3 ) in Theorem 2.3. This fact implies
the version of the following theorem, where α(G) is exchanged for ι(G)/n.
(For analogous results with ϑ(G), see [8].)
THEOREM 3.1For any graph G,
a)
Applying the variable transformation described in (3) to the program in
Lemma 2.1, as an immediate consequence we obtain an analogue of Theorem
2.2 in [8].
THEOREM 2.3The optimal value of the program
n
X
dij + 1
dij = −1 ({i, j} ∈ E(G)),
p
,
(P3 ) :
sup
n
D
= (dij ) ∈ S+
(dii + 1) · (djj + 1)
i,j=1
Miklós Ujvári
α′ (G) := 1 +
X
{i,j}∈E(G)
b)
2/n
p
≤ α(G);
(δi + 1) · (δj + 1)
α′′ (G) := 1 +
µG
≤ α(G).
ΛG + 1
We will apply Theorem 2.3 in the next section for obtaining lower bounds
in the stable set problem.
Proof. By Exercise 11.14 in [4] we have µG ≤ ΛG . Using this relation it is
immediate that
n
n
≤ α′′ (G) ≤
.
ΛG + 1
µG + 1
Operations Research Reports No. 2014-03
Operations Research Reports No. 2014-03
Bounds on the stability number of a graph via the inverse theta function
11
We will show that the inequalities
n
X
n
i=1
1
≤ α(G)
δi + 1
1
2
1
p
+
,
√
≤
δi + 1 δj + 1
δi + 1 · δj + 1
′
α (G)
(11)
n
X
i=1
i∈V (G1 ), j∈V (G2
i=1
(12)
Using the arithmetic mean-harmonic mean inequality, it is easy to show that
≥
≥
1
1 + (nµG )2
n
{i,j}∈E(G)
,
1
δi + 1 + δj + 1
X
(δi + 1 + δj + 1) .
{i,j}∈E(G)
n
X
1
+
δi + 1
X
(δi + 1 + δj + 1)
!2
≤ α′ (G)n.
2
p
≤ n,
(δi + 1)(δj + 1)
{i,j}∈E(G)
X
which follows immediately applying (11).
b) is obvious, as
α′ (G1 + G2 ) ≤
≤
Hence, to prove (12), it is enough to verify that
nµG (µG + 1) ≥
1
√
δi + 1
In other words, we have to prove the inequality
i=1
α′ (G)
(δi + 1)(n − 1 − δi ),
that is (without loss of generality assuming G1 = G2 = G)
n
X
n
.
µG + 1
X
i=1
2
p
≤ α′ (G1 )n2 + α′ (G2 )n1 ,
(δ
+
1)(δ
+
1)
i
j
)
On the other hand, we will verify the relation
4
1+ ·
n
n
X
THEOREM 3.2With the lower bounds ℓ = α′ , α′′ we have
a) ℓ(G1 + G2 ) ≤ ℓ(G1 ) + ℓ(G2 ),
b) ℓ(G1 + G2 ) ≤ max{ℓ(G1 ), ℓ(G2 )},
for any graphs G1 , G2 .
X
1
.
δi + 1
α′ (G) ≥
i=1
(δi + 1) ≥ n ·
Proof. Case 1: ℓ = α′ . a) Rewriting the statement, we have to verify
n
1 X 1
≤ 1+ ·
· (n − 1 − δi )
n i=1 δi + 1
=
n
X
The following theorem describes additivity properties of the bounds α′ , α′′ .
(For analogous results, see [9].)
by the Caro-Wei theorem (see e.g. [8]).
First, using the obvious inequality
we obtain
(n − 1 − δi ) ·
and thus is a consequence of the Cauchy-Schwarz inequality. The proof of
(12) is complete, as well. hold also, from which the theorem follows, as
i=1
Miklós Ujvári
holds. This inequality can be rewritten as
X 1
n
≤ α′ (G) ≤
µG + 1
δ +1
i=1 i
n
X
12
α′ (G1 )n1 + α′ (G2 )n2
n1 + n2
′
max{α (G1 ), α′ (G2 )}
hold.
Case 2: ℓ = α′′ . With
{i,j}∈E(G)
u(G) := ΛG + 1,
Operations Research Reports No. 2014-03
Operations Research Reports No. 2014-03
Bounds on the stability number of a graph via the inverse theta function
13
it is shown in [9] that the inequalities
u(G1 + G2 ) ≥
u(G1 + G2 ) ≥
max{u(G1 ), u(G2 )},
u(G1 ) + u(G2 )
n 2 µG 1 + n 1 µG 2
≤ max{u(G1 ), u(G2 )} − 1,
n1 + n2
which holds true, as µG ≤ ΛG for any graph G, by Exercise 11.14 in [4]. See [9] for an application of this type of results in strengthening the bounds
when the graph or its complementer is not connected.
Upper bounds on α(G)
In this section we introduce two variants of the inverse theta number. They
constitute bounds for the stability numbers of G and G.
is well-known, see for example [2]. Moreover, applying the technique used in
the proof of Theorem 2.2 we obtain the analogous
THEOREM 4.1The primal-dual semidefinite programs
′
b11 − b′ii = 0 (i = 2, . . . , n),
′
′
b′ = 0 ({i, j} ∈ E(G)),
(P2 ) :
sup −tr B ,
ij
n×n
n
tr ((J − I)B ′ ) = 1, B ′ = (b′ij ) ∈ S+
∩ R+
,
′
tr C = n,
c′ ≤ γ ′ ({i, j} ∈ E(G)),
(D2′ ) :
inf γ ′ ,
ij′
n
C = (c′ij ) ∈ S+
, γ′ ∈ R
have common attained optimal value n/(n − ι′ (G)). ϑ′ (G) ≥ ι′ (G)/n, α(G),
we have also
p
1
1 + 4(ι′ (G) − n) + 1 ≥ ι′ (G)/n, α(G)
2
The programs have common attained optimal value by standard semidefinite
duality theory (see for example [7]), we will denote this value by ι′ (G).
Obviously, ι′ (G) ≤ nϑ′ (G), where ϑ′ (G) is a sharpening of the theta number, due to McEliece, Rodemich, Rumsey, and Schrijver (α(G) ≤ ϑ′ (G) ≤
ϑ(G), see for example [2]), defined as
tr Y ′ = 1,
′
= 0 ({i, j} ∈ E(G)),
ϑ′ (G) := sup tr (JY ′ ) yij
.
n×n
n
Y ′ = (y ′ ) ∈ S+
∩ R+
ij
In other words, we have the inequality
Operations Research Reports No. 2014-03
′
nii = 1 (i = 1, . . . , n),
1
′
′
′
n
≤
ν
({i,
j}
∈
E(G)),
=
min
ν
ij′
1 − ϑ′ (G)
n
N = (n′ij ) ∈ S+
, ν′ ∈ R
Besides the mentioned relations
Let us consider the primal-dual semidefinite programs
′
zij ≤ −1 ({i, j} ∈ E(G)),
′
′
(P ) :
inf n + tr Z ,
′
n
Z ′ = (zij
) ∈ S+
,
′
mii = 1 (i = 1, . . . , n),
m′ = 0 ({i, j} ∈ E(G)),
(D′ ) :
sup tr (JM ′ ),
ij′
n×n
n
∩ R+
.
M = (m′ij ) ∈ S+
n
1
≤
,
′
n − ι (G)
1 − ϑ′ (G)
Miklós Ujvári
an analogue of (10).
The reformulation
hold. The statements a) and b), respectively, are straightforward consequences of these inequalities, after applying (1): For example, a) can be
reduced this way to the inequality
4
14
(13)
as the following theorem shows. (For analogous results with ι(G), see [10].)
THEOREM 4.2For any graph G,
p
1
α(G) ≤
1 + 4(ι′ (G) − n) + 1
2
holds.
Proof. Let S be a stable set in G with cardinality #S = α(G). Let us define
the matrix M ′ := (m′ij ) ∈ Rn×n the following way: let m′ij := 1 if i, j ∈ S or
i = j, and let m′ij := 0 otherwise. Then, the matrix M ′ is a feasible solution
of the program (D′ ) with corresponding value
(#S)2 + n − (#S) ≤ ι′ (G).
Operations Research Reports No. 2014-03
Bounds on the stability number of a graph via the inverse theta function
15
Hence, the statement follows. Miklós Ujvári
a) Let S1 , . . . , Sk be a stable set partition of V (G) such that the cardinality
of the index set {i : #Si ≥ 2} is maximal. Then,
The bound in Theorem 4.2 implies
α(G) ≤
16
S := ∪ki=1 {Si : #Si = 1}
p
ι′ (G),
is a stable set in G. Furthermore, the matrix
and also, by ι′ (G) ≤ ι(G), the relations
p
p
1
α(G) ≤
1 + 4(ι(G) − n) + 1 ≤ ι(G)
2
from [10]. It is an open problem whether any of these bounds can be less than
ϑ(G) or even ϑ′ (G) for some graphs.
Another variant of the inverse theta number leads to new bounds on the
stability numbers of G and G.
Let us define ι′′ (G) as the common attained optimal value of the primaldual semidefinite programs
′′
mii = 1 (i = 1, . . . , n),
m′′ = 0 ({i, j} ∈ E(G)),
(P ′′ ) :
inf tr (JM ′′ ),
ij′′
n
M = (m′′ij ) ∈ S+
,
′′
zij = 1 ({i, j} ∈ E(G)),
(D′′ ) :
sup n − tr Z ′′ ,
′′
n
Z ′′ = (zij
) ∈ S+
.
(See, for example, [7] for standard semidefinite duality theory.)
Both formulations constitute bounds in the stable set problem. On the
primal side, we have
THEOREM 4.3For any graph G, the inequalities
M Si
i=1
is feasible in (P ′′ ) with corresponding value #S ≤ α(G), which completes the
proof of statement a).
b) Let S0 be a stable set in G with cardinality α(G). Then, similarly as in
the proof of statement a), the matrix
M S0 +
X
M{i}
i6∈S0
is a feasible solution of the program (P ′′ ) with corresponding value n − α(G).
This finishes the proof of statement b), too. The dual version of Theorem 4.3 is immediate, now.
′′
THEOREM 4.4Let the matrix Z ′′ = (zij
) ∈ Rn×n be a feasible solution of
′′
′′
n
′′
the program (D ), that is let Z ∈ S+ such that zij
= 1 for {i, j} ∈ E(G).
Then, tr Z ′′ ≥ n − α(G), α(G) hold. For example, for the cherry graph
G0 := ({1, 2, 3}, {{1, 2}, {1, 3}}),
a) ι′′ (G) ≤ α(G),
the optimal solutions of (P ′′ ) and (D′′ ), respectively,
1 0
0
0 0 0
M0′′ := 0 1 −1 , Z0′′ := 0 1 1
0 −1 1
0 1 1
b) ι′′ (G) ≤ n − α(G)
hold.
Proof. Let us introduce the notation
1
− 1
MS := (mij ) ∈ Rn×n , where mij :=
#S−1
0
k
X
if i, j ∈ S, i = j,
if i, j ∈ S, i 6= j,
otherwise,
for S ⊆ V (G).
Operations Research Reports No. 2014-03
show that by Theorems 4.3 and 4.4 α(G0 ) ≤ 2 and α(G0 ) ≥ 1.
On the negative side, ι′′ (G) = 0 if V (G) has a partition S1 ∪ . . . ∪ Sk where
all the sets Si are stable with cardinality at least 2 (see the proof of Theorem
4.3). In this case the bounds described in Theorems 4.3 and 4.4 are trivial.
It is an open problem to characterize the graphs G with ι′′ (G) = 0.
Operations Research Reports No. 2014-03
Bounds on the stability number of a graph via the inverse theta function
17
References
1. Knuth, D., The sandwich theorem. Electronic Journal of Combinatorics, 1:1–48, 1994.
18
Miklós Ujvári
Miklós Ujvári
H-2600 Vác, Szent János utca 1. HUNGARY
2. Laurent, M. and Rendl, F., Semidefinite programming and integer
programming. In: Aardal, K. et al., editors., Handbook on Discrete
Optimization, Elsevier B.V., Amsterdam, pages 393–514, 2005.
3. Lovász, L., On the Shannon capacity of a graph. IEEE Transactions
on Information Theory, IT-25(1):1–7, 1979.
4. Lovász, L., Combinatorial Problems and Exercises. Akadémiai Kiadó,
Budapest, 1979.
5. Rózsa, P., Lineáris Algebra és Alkalmazásai.
dapest, 1991.
Tankönyvkiadó, Bu-
6. Strang, G., Linear Algebra and its Applications. Academic Press, New
York, 1980.
7. Ujvári, M., A note on the graph-bisection problem. Pure Mathematics
and Applications 12(1):119–130, 2002.
8. Ujvári, M., New descriptions of the Lovász number, and the weak
sandwich theorem. Acta Cybernetica, 20(4):499–513, 2012.
9. Ujvári, M., Strengthening weak sandwich theorems in the presence of
inconnectivity. Submitted to Acta Cybernetica, 2013.
10. Ujvári, M., Applications of the inverse theta number in stable set
problems. Accepted for publication at Acta Cybernetica, 2014.
Operations Research Reports No. 2014-03
Operations Research Reports No. 2014-03
Selected Operations Research Reports
2010-01 Miklós Ujvári: Strengthening weak sandwich theorems in the
presence of inconnectivity
2010-02 Tibor Illés, Zsolt Csizmadia: The s-Monotone Index Selection
Rules for Pivot Algorithms of Linear Programming
2010-03 Miklós Ujvári: Four new upper bounds for the stability number
of a graph
2011-01 Miklós Ujvári: Applications of the inverse theta number in stable
set problems
2011-02 Miklós Ujvári: Multiplically independent word systems
2012-01 Tibor Illés, Rihárd Molnár-Szípai: On Strongly Polynomial
Variants of the MBU-Simplex Algorithm for a Maximum Flow Problem
with Nonzero Lower Bounds
2012-02 Tibor Illés, Adrienn Nagy: Computational aspects of simplex
and MBU-simplex algorithms using different anti-cycling pivot rules
2013-01 Zsolt Csizmadia, Tibor Illés, Adrienn Nagy: The s-Monotone
Index Selection Rule for Criss-Cross Algorithms of Linear Complementarity Problems
2013-02 Tibor Illés, Gábor Lovics: Approximation of the Whole ParetoOptimal Set for the Vector Optimization Problem
2013-03 Illés Tibor: Lineáris optimalizálás elmélete és pivot algoritmusai
2014-01 Illés Tibor, Adrienn Nagy: Finiteness of the quadratic primal
simplex method when s-monotone index selection rules are applied
2014-02 Adrienn Nagy: Finiteness of the criss-cross method for the linear programming problem when s-monotone index selection rules are
applied
© Copyright 2024 ExpyDoc
