FOR GRAPH; : _

"fhesis for the Degree of Ph'. D.
WCHKGRR STATE UNWERSFTY
DANEEL HURNG~CHAO MENG

2974

    
 

LIB R A R Y

Lik‘higan St :33 '
"nivcrsu i;

U I j”

w...—

This is to certify that the
thesis entitled
MATCHINGS AND COVER INGS

FOR GRAPHS

presented by

Daniel Huang-Chao Meng

has been accepted towards fulfillment
of the requirements for

Ph.D degree in Mathematics

 

Major professor

0-7639

 
   

y amome w ‘3

HUAG & SflNS'

A max mum me.

9935.“?! PEPE”

 

—.:.-.-—~ . A

 

 

 

 

  
  
  
  
  
 
  
    
 
  
 
  

‘ \
4, 1n 331.14.» l - ' v‘ 1.. - .'-:~f¢r'>‘-.rr}f-1 has
P

.
.

1 devo-‘rv'? ' :Amclgx of

..

.
,
..
'0

I of laden-inf" ..- l i ~.-;i~-r‘.r:n7' i: :‘n be which
the nu‘nmur: - s we-» ‘. e . In' t; and:
"a [ton has, l'na-r '. (-7- as , i'». '. 1;; .'.. :-v, Hut. is to

gtgf edger, \.':;.t_r. rap. 1. -.>»‘~.‘t’ ‘— _. a graph. or
1

‘4. Of w':zti"r'-‘- u ‘t f>\"i‘ (:1; ' o . :,.:J 01' 5 graph

. “1511 thr u hi , rl‘v m . {'Js'lfll- cardinality.
‘ 7n
this rllt‘fil‘? 'r‘l nasty m:*.~..v.-.~ - Awnings and

“gigs an: exrsrcer: ’c mum. 1 wt- Uy 5211? thug} "

"‘ t.
Ngw
‘Mr'

&

. and the intetrfilailmis. burp-en . :cmaa’.» an;

era invariance. A we}; know aegzmu‘ n! Go!

 
 
       
   
    
  

 
 

flutes airman cwors‘and mxtum niaphzap is»
H1931“ «3 ratio mm the mag-yuan w
sip. max-.Gathi my..." Mag-go“ _,

,‘ _ _ .'

'_ .13 variant): ways, ‘I' 7 ~‘ ‘. ~ "5‘ ft:-
_ t.-

‘ i

   

ABSTRACT

MATCHINGS AND COVERINGS
FOR GRAPHS

By
Daniel Huang-Chao Meng

In graph theory, an extensive amount of research has
been devoted to the study of maximum matchings, namely of
sets of independent edges or independent vertices which
have the maximum cardinality possible. Similarly much
attention has been given to covering properties. that is to
sets of edges which cover all the vertices of a graph, or
to sets of vertices which cover all the edges of a graph
and in which the sets have the minimum possible cardinality.

In this thesis the basic notions of matchings and
coverings are extended to maximal matchings and minimal
coverings, and the interrelations between matchings and
coverings are investigated. A well known theorem of Gallai,
which relates minimum covers and maximum matchings is
extended in various ways.

In particular a ratio called the edge Gallai ratio and
one called the vertex Gallai ratio are introduced. and

facilitate the study of matchings and coverings. Precise

 

5”
(V
e

Daniel Huang-Chao Meng

upper and lower bounds are obtained for these ratios.

A final section is devoted to generalizations of the
concepts of edge dominating numbers and vertex dominating
numbers.

There are essentially twelve principal graphical
parameters discussed in this thesis, and a useful table is
provided listing their values for numerous well known graphs

and classes of graphs.

 

MATCHINGS AND COVERINGS FOR GRAPES

BY

Daniel Huang-Chao Meng

A THESIS

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY
Department of Mathematics - ‘:.:j

1974

   

 

v
| I

   
     
  
 
   
     

1| '.
.‘4 '
v.
' ‘l

i“! '15». ";. 4- _. fl

‘i ., . ‘ i
N". ”‘f i» ' r ' .‘ o.‘ ' i . -| I. n ‘ ‘— ‘
II P ‘ ".'- ’ I j ‘

“‘41-" of Patient

-.r
9

.131 than... 3 ;

,"fi‘. 1‘. «2,31 '3 '1' . My "inf-e: "_ ":37" ‘ff. ‘1'" 1‘] the
.Iopllem; «"Hc'.‘ l;' {-1 1' ' ‘ :":~4.H1m,
, A
l' £1

'I-- 7“” gratit‘..-u.' (QM-t . ' '; {wtrt xsarv '5. Mummy» for
r- "H , _
V ‘ ‘ Oting Ch" ”’5" " ‘ 3 1?,1..".', mm! for in 3 mar“,- userul

3 during 27,, ’H'vmiv‘w 23.3,
T'J'Ould also 1 'unr- ‘L; fit .- '39 v. \‘lti'; ‘. ‘1. L611).

" ““' 'u: wearing on .

ACKNOWLEDGMENTS

I wish to express my deepest gratitude to Professor
E. A. Nordhaus for including me to his "academic family".
Special thanks must go to him for his many hours of patient
guidance. unfailing interests and timely advice in the
development and completion of my program.

My gratitude also goes to Professor B. Grunbaum for
suggesting the topic of this thesis and for his many useful
comments during its preparation.

I would also like to thank Professors L. M. Kelly,

B. M. Stewart, W. E. Kuan and M. J. Winter for serving on
my advisory committee. Finally. my thanks go to the
Mathematics Department of Michigan State University for

their financial support during the writing of this thesis.

 

TABLE OF CONTENTS

1 igu:c

Pfiéhapter”

_"
I

   
    
  
   

TEE-‘Introduction . . . . . . . . . . . . . . .

“3¥2§'Zfliatorical Survey . . . . . . . . . . . .

~ ‘9'}:33 . ,‘(Edge MatChings o s s o s o I o o I U I U 0

A4.

w ‘45 [Edge Coverings . . . . . . . . . . . . . .
1 '5. Edge Matchings and Coverings .~. . . . . .
.f;fi§§53Vertex Coverings and Independent sets of

' I ‘. Avertices I O O I O C I O O O O I I O I I .

. i 4% .ynomating Numbers I Q I C C C C C I . O C

i] 3, — »
”“5" "v
gr.at i ‘ ‘- ‘. ~x ‘ '
.., .
‘ag , L J. -

Vile oprarameters for Certain Classes of Graphs.

Page

14
53
6'3
81
89‘
104
106

 

Figure
1.1
3.1
3.2

3.3
3.4

3.5
3.6
3.7
4.1
4.2

5.1
5.2
5.3

5.4

5.5

7.1
7.2

LIST OF FIGURES

T he whee 1 W6 I I I I I I I I I I I I I I I I
A minimum matching which is not hereditary.

A graph illustrating a sharp lower bound
When 6(G) a 1 I I I I I I I I I I I I I I

Existence of a T vertex w adjacent to XN. .

Two S vertices x and y joined by a strong
edge I I I I I I I I I I I I I I I I I I I I

A T vertex joining two 8 vertices . . . . .

An edge (x,y) not incident with 3 vertices.

A weak vertex Vi between e0 and e1. . . . .
The degree sequences of G1 and G2 . . . . .
A maximum covering failing to have

property (P* . . . . . . . . . . . . . . .
A counter example . . . . . . . . . . . . .

The types of outer components . . . . . . .

A graph not of Gallai type relative to
matchings . . . . . . . . . . . . . . . . .

A graph not of Gallai type relative to
coverings . . . . . . . . . . . . . . . . .

A block not of Gallai type relative to
mtchings I I I I l I I I I I I I I I I I I

A graph illustrating 30U(Gl) < OOU(GI). . .

A graph illustrating ODL(GZ) < BOL(GZ). . .

Page

14

27
33

34
38
39
43
S6

59
64
66

72

72

74
92

92

  
 
    
    

.. P880
. .5
.é"5.$' . ‘1‘](G) I p’Z a s s s s o s s s a s o s I s s 93

Liufifih3' A graph illustrating 81U(G) < “10(6) . . . . 95

.‘ 3;5 Three end vertices of C joined to a single

’ ‘.‘ ‘5“ vertex of w. . I C I I I I I I I I I . I I I 97
-;.:?s6 Two pairs of end vertices of C joined to two

' “' distinct vertices of W . . . . . . . . . . . 97

An end vertex of C2 joined to a vertex u11 . 99.

a

A

4
J)" I)
j"'\ .,;

fffif’ >_v _ . » ‘ nit .‘I'r-rf“!
. “1.1. -‘ . . . ‘1'"
.7 .. ‘ i . , . ,...l.. :

‘\

_ "

5 ermin- rv ,- mw. ~ , '4
«IL .a, . ... . .. . . . ,

’s for em? 121.13.}:1’3‘:

'fi en min rum anteniag ‘IVL # ~e I;

:21 ' .

   

“‘74

CHAPTER 1

Section 1.1
INTRODUCTION

In graph theory certain concepts have been emphasized
and extensively studied. Examples which readily come to
mind are the genus of a graph, which might more appropriately
be called the minimum genus. the edge matching number asso-
ciated with maximum matchings. and the edge covering number
associated with minimum edge covers. Recently it was found
fruitful to consider the concept of the maximum genus of a
graph [16].

As Professor Branko Grunbaum [13] has remarked. "People
are too frequently preoccupied with maximum matchings and
minimum coverings. It is certain that a non-discriminatory
approach should lead to a bevy of new results on matchings
and coverings and in many other areas of graph theory."

This thesis has been motivated by such considerations, and
we investigate certain general properties of matchings and
coverings and find that it is possible to provide meaningful
definitions for minimum matchings and maximum coverings.

Some results on minimum matchings have already been noted

by Grunbaum. We extend these results to arbitrary matchings
and coverings.

In many areas of graph theory. one could see if useful
and meaningful results could be obtained by a change in the
point of view. such as replacing the word “maximum“ by
"minimum“ or vice-versa. This certainly opens a new door
to the interested researcher. Until recently, general
matchings and coverings have not been carefully examined,
since it appears that almost the entire emphasis has been
placed on maximum matchings and minimum coverings.

Definitions of terms as well as some of the notation
employed in this thesis are presented in Section 1.2. A
survey of known results related to the material of this
thesis is presented in Chapter 2.

The first section of Chapter 3 discusses edge matchings,
and a condition for a matching to be a minimum. The next
section determines non-trivial lower bounds for the number
of edges in a minimum matching in terms of the maximum
degree[5(G) of G. These bounds differ when the minimum
degree 6(G) 2 1 and when 6(6) 2 2. Section 3.3 deals with
the enumeration of minimum matchings for n-th subdivision
graphs.A Precise formulas are obtained for the number of
edges in such matchings.

In Chapter 4, a discussion is made of edge coverings.

Certain general properties of maximum coverings are

 

developed, and in Section 4.2 an upper bound for the number
of edges in a maximum cover is given in terms of a degree
sequence. In Section 4.3 a sufficient condition for a
covering to be a maximum is stated and proved.

Chapter 5 deals with the inter-relationship between
matchings and coverings. In Section 5.1 certain graphs
of Gallai type relative to matchings or coverings are char-
acterized. In Section 5.2 we define an edge Gallai ratio
for a graph C and obtain sharp upper and lower bounds for
this ratio.

In Chapter 6, we extend some of the ideas developed
for edge matchings and edge coverings to independent sets
of vertices and to vertex coverings. In Section 6.1 an
extension of Gallai's theorem is obtained. This result is
that for any graph G of order p, aOU(G) + BOL(G) = p. In
contrast with the case of edge matchings and edge coverings,
where all values between the minimum and the maximum values
of the parameters are assumed, for vertex coverings and
independent set of vertices "gaps" may occur in the para-
meter values. In Section 6.2 we define a vertex Gallai
ratio for a graph G and obtain upper and lower bounds for
this ratio.

In Chapter 7, dominating numbers are discussed, and
edge dominating sets and vertex dominating sets are in-

troduced. The relation between minimal edge dominating

 

sets and edge matchings and also between minimal vertex
dominating sets and independent sets of vertices are studied.
Finally, a table is provided giving the values of all of
parameters considered in this thesis for certain well known
special graphs and special classes of graphs.

Finally, a bibliography lists references which have
been useful in the preparation of this thesis.

Section 1.2
BASIC TERMINOLOGY

In this section we present some of the basic definitions
and notations which are used in the following chapters. For
additional graph theory terminology not explicitly given in
this thesis, one may refer to standard texts such as Behzad
and Chartrand [4], Berge [3], or Harary L14].

A gggph G is a non-empty set V together with a set E of
two-element subsets of V. The set V is referred to as the
vegggx (or point) ggg of G, and each element of V is called
a vertex (or point). The set E is referred to as the edge
(or line) sg; of G. The members of the edge set E are called
edges. In general, the vertex set and edge set of a graph
G will be denoted by V(G) and E(G) respectively. The graph
G is called finite if V(G) and E(G) are both finite. In
this thesis all graphs, unless otherwise noted. are assumed

to be finite, undirected, and without loops or multiple edges

 

and ordinarily having no isolated vertices.

The ggggg of a graph G, denoted by V(G) or more
simply by IGI, is the number of elements in V(G). If
|V(G)I = p and |E(G)| = q, we say that G is a (p,q) graph.
A graph G is called gmpgy if E(G) is the empty set. The
degree (or valency) of a point of G is the number of edges
of G incident with v and is denoted degGv, or simply by
deg v. In particular, 6(6) and [3(6) are repeatedly used to
denote respectively the minimum and the maximum degree of
the vertices of G. A graph H is a subgraph of a graph G if
V(H) E_V(G) and E(H) E E(G). The subgraph induced by a set
U of vertices of G, denoted by <U>, is that graph which has
U as its vertex set and whose edge set consists of all edges
of G which join two vertices of U. Similarly, if F is a
non empty subset of E(G), then the subgraph <F> induced by
F is the graph whose vertex set consists of those vertices
of G incident with at least one edge of F and whose edge set
is F. If v is a vertex of G then G-v denotes the graph
<V(G) - v>, and in general if S is a proper subset of V(G)
then G - S represents the graph <V(G) - S>. Two vertices
u and v of a graph G are said to be connected if there
exists a u-v path in G, the graph G itself is connected if
every two of its vertices are connected.

Given any X E V(G), there is a largest subgraph H of

G such that X = V(H), that is, for u, vEX, (u,v)€E(H) if and

_-a‘--I‘V‘V .

only if (u,v)€E(G). We call this subgraph H the resgric-
gigg G/X of G to the vertex set X. There are several spe-
cial classes of graphs to which we will frequently make
reference. A graph of order n which is a path or a cycle

is denoted by Pn or On respectively, and the number of edges
in a path or a cycle is called its lenggh. An acyclic graph

is a graph G with no cycles and is a tree if G is also

 

connected. If G is disconnected and acyclic, G is called a
forest. The complete graph KP has every pair of its p
vertices adjacent. A bipartige graph G is a graph whose
vertex set V(G) can be partitioned into two disjoint subsets
V1 and V2 such that every edge of G is of the form(v1y2)
where vi 6 V1, 1 = l, 2. If V1 and V2 have m and n points
and G'mn edges, we say that G is a cgmplete bipartite graph
and write G = K(m,n). A star graph or claw is a complete
bipartite graph K(l,n). For n 2 4, the wheel Wn is defined
to be the graph K1 + Cn-l'

Figure 1.1. The Wheel W6
A graph Sn(G) referred to as the n-th subdivision graph of

G is obtained by replacing every edge of G by a path of
length n + 1. When n = 1, this graph is called the subdivi-
sion graph of G and is denoted by S(G)

AI.

A set M of edges of a graph G is called a magching sgg
provided each vertex of G is incident with at most one edge
contained in M. Thus M is a set of independent edges. A
matching set M is called a matching of G provided there is
no matching set of G which properly contains M.

If M is a matching for G, IMI denotes the number of
edges in M. The parameters 81L(G) and 81U(G) are used to
denote respectively the minimum and maximum number of edges
in any matching of G. If M is any fixed matching of G, an
edge e in M is called a strong gggg. Obviously two strong
edges are never adjacent. If edge e is not in M, we refer

to it as a weak edge. These concepts are of course depend-

 

ent on the choice of the matching M. A vertex incident only

to weak edges relative to M is said to be a weak vergex. A

 

vertex incident with a strong edge and not incident with any

weak edge is called a strong vertex (relative to M.)

Finally, a vertex incident with a strong edge and also to

at least one weak edge (relative to M) is said to be neutral.
Let X be any subset of E(G). An alternative pggh of

(G,X) is one whose successive edges are alternatively in X

and not in X. When an orientation of the vertices of a

path is made, the first and last edges of a path are called

its germinal ggg§_. The terminal vertices of the path

consist of the vertex incident to the first edge but not the

second, and the vertex incident to the last edge but not to

ll '
.7“. '

the preceding edge. An augmenting pggg (G,X) is an alter-
nating path (G,X) whose terminal vertices are incident to no
edge of X. If (G,X) has no augmenting path, X is called
unaugmentable. The concept of an augmenting path has been
used in characterizing maximum matchings [2].

A set C of edges of a graph G is an gggg covering ggg
of G provided each vertex of G is incident with at least one
edge that belongs to C. An edge covering set C is called an
gggg covering of G or simply a coverin , provided there is
no edge covering set of G which is properly contained in C.

If C is a covering of G we denote by ICI the number
of edges in C, and by a0L(G) and a0U(G) the minimum and
maximum number of edges respectively, in any covering of G.
An alternative path of (G,C) is a geducing pggh if (1) its
terminal edges are in C, (2) its terminal vertices are in-
cident to edges of C which are not terminal edges of the
path. If (G,C) possesses no reducing path, C is called an
iggeducible cover.

A graph G having the property that corresponding to an
arbitrary edge covering C of G there exists at least one
matching M such that [Cl + IMI = |V(G)| is called of Gallai
gypg gglativg £9 coverings. Similarly, a graph is said to
be of Gallai gypg relative g9 matchings if it has the prop-
erty that for every edge matching M of G there is at least

one edge covering c of G with | M I + |c| = |V(G)|.

WK" ' "" \"“—

I.“

CHAPTER 2
HISTORICAL SURVEY

In this chapter we summarize some of the most impor-
tant known results bearing on matchings and coverings of
graphs. and related results.

In 1957. C. Berge [2] used the technique of alternative
paths to characterize a maximum matching. He proved that a
matching M has maximum cardinality if and only if there
exists no argumenting path in (G.M).

According to this theorem, if an edge matching M is
given, one can decide if this matching is a maximum matching
by searching for all alternating paths starting at a weak
vertex. This method has been improved by Edmonds [8] and
adapted to a computer search by Witzgall and Zahn [26].

They defined a vertex v to be an outer vertex, rooted at u.
if u is a weak vertex which is Joined to v by an alternating
path of even length. (In particular. all weak vertices are
regarded as outer.) The reason for considering outer ver-
tices becomes evident if one examines an augmenting path
connecting two weak vertices u1 and uz. Let v1 and v2 be

the neighbors of u1 and “2 within the augmenting path.

9

 

 

10

Then v2 is an outer vertex rooted at u1 and v1 is an outer
vertex rooted at “2' This leads to a reformulation of
Berge's result, namely that a matching is maximum if and
only if no weak vertex u is adjacent to an outer vertex
which is rooted at a weak vertex different from u.

For the purpose of establishing maximality or non-
maximality of a matching it is therefore sufficient to
search for all outer vertices. This is an improvement over
searching for all alternating paths, since there are in
general more alternating paths emanating from weak vertices
then there are outer vertices.

In 1957, Norman and Rabin [18] presented a method for
finding in a graph G a minimum edge cover, employing the
concept of a reducing path. They proved the theorem that
an edge cover C has minimum cardinality if and only if
there exists no reducing path in (G,C).

This theorem gave rise to an algorithm for finding a
minimum cover. Norman and Rabin also show that the maximum
matching problem and minimum edge cover problem are equiv-
alent. This, of course serves the same purpose as the well
known theorem of Gallai. which states that for any graph G
of order p we have “OL + BOU = p, and for any graph having
no isolated vertices, alL + BlU = p.

J. Weinstein [25] in 1961 found a non-trivial lower

bound for BlU(G) in terms of the maximum degreeZ§(G) of G.

11

and states two theorems which also involve the minimum
degree 6(G).

(2) For graph with 6 Z 2, 2p 5 (2 + max (4#3) ' 31U(G))

(1) For graphs with 6 Z l. p < (l +A) ' 81U(G)

Using the technique of ”alternating paths" Grunbaum
[12] proved the following two intermediate theorems for
matchings and coverings.

(1) For every graph G and every integer 81 satisfying
BIL S 81 5 BlU’ there exists an edge matching M of G such
that IMI

81.
(2) For every graph G and every integer a1 with
alL 5 a1 _ alU there exists an edge cover C of G such that
IC |= a1.
These results are of interest since they show that no
gaps are possible in these parameter values. We will show
later that gaps can occur in the parameter values for vertex
covers and maximal independent sets of vertices.
It is evident that BID 5 [p/Z] and that M is an edge

matching of G such that IMI = p/Z if and only if M is a l -
factor of G. Grfinbaum [13] has also shown that 810 5 2le

and that there exists a j - connected graph G with ar-
bitrary large order, such that BlL(G) = LJ-g-l].

No general procedure or algorithm has so far been
developed to determine the number of edges in an arbitrary

matching or in an arbitrary covering. M. J. Stewart [24],

12

has determine the number of edges in a maximum matching for
the n-th subdivision graph Sn(G). This number, BlU(Sn(G))'
depends on q = IE(G)I, on the parity of n. and sometimes
also on the parameter $1U(G), namely,
(1) Let G be a connected (p,q) graph. Then
81U(SZK(G)) = kq + 61U(G).'
(2) Let G be a connected (p,q) graph. Then
BlU(SZK-1(G)) = E: + p - q §€h§r$§32.tree'
Let K(p1. p2. . . ., p3) denote the complete j - partite
graph with sets of vertices containing p1, p2, . . . .. pj
elements the notation being such that p1 5 pz 5 . . . 5 p.,

3

J
and let p = 2 pi' Then we have

i=1
alU(K(p1. p2. . . .. pj)) = min (CF/2]. p-pj)
and
BiL<K<Pi- p2. . . .. pj) = max (pj_1. {‘P'Pj’/2})
The first result is due to Chartrand, Geller. and Hedetniemi
[6], and the second to B. Grunbaum [13].

Let Id denote the graph of the d-dimensional cube.
Forcade [9] proved that 81L(Id)/V(Id) is a non-increasing
function of d and that lim 81L(Id)/V(Id) = 1/3

d-9N

Finally, let G be a connected (p,q) graph and let LG
denote the line graph of G and TG the total graph of G.

R. P. Gupta [11] proved the following formulas:

13

   
   
  
 
 
 
  
   
   

Bou<LG> a a1U(G)
a0L(LG) = q — 81U(G)
abL(LG) ‘ °iL(G)
scum) = p - anfc)

, a0L(TG) a Cl + o'11‘(G)
- figfj':

3 LG =

Guf . Inc ) [q/ZJ
ufitri‘ alL(LG) a {q/Z}

' Ci“ ‘ I ‘ ' Blucrc) a [$3
HOUca a1L(TG) . Egg

5} \';‘.v" :u.

QUAs i “1L(G)5 B00““) 5 L3 /2 ' “1L(G)J
mchsany of these results could be extended to arbitrary

‘.“. .Efilngs and coverings. Line graphs will be considered

 

CHAPTER 3
EDGE MATCHINGS

Section 3.1. In 1957, Berge [2] gave a necessary and
sufficient condition for determining whether or not a given
matching is a maximum, and provided an algorithm for
constructing a matching with the maximum number of edges.
However, to find a necessary and sufficient condition for a
given matching to be a minimum appears to be a difficult
question to answer. One reason for this is that a minimum
matching is not hereditary. in the sense that if H is a
subgraph of G, the inequality 81L(H) 5 BlL(G) need not be
valid. For example, consider the graphs G and H shown in

the figure.

 

 

 

 

Figure 3.1. A minimum matching which is not hereditary.
Here H is a subgraph of G, yet 81L(G) = l, and 81L(H) = 2.

Throughout this chapter we will assume that the word

"matching"refers to an edge matching. Furthermore, since

14

 

‘5 HJ '
.58“;

15

an isolated vertex cannot be covered by any edge, we assume
that the graphs considered have no isolated vertices.

In this section we prove a sufficient condition for a
matching to be minimum. Let M be any matching of a graph
G(p,q), and let W, S, and N denote the sets of weak vertices,
strong vertices and neutral vertices of G, respectively,
relative to M.

First we have the following elementary observation.

Theogem 3.1. If IN! S 1, then M is a maximum matching.
Proof: If IWI = 0, since p = INI + IWI + ISL then

p = INI + '8'. Now INI + ISI ZIMI,
since every vertex incident with an edge in M is a strong
or a neutral vertex. Thus p = ZIMI and IMI = plz. so M
is a maximum matching.
Ifl WI = 1, then p = ZIMI + l, and IMI = (p-l)/2= Lp/ZJ'

Thus M is again a maximum matching.

The converse may not be true, since M can obviously be
a maximum matching even when |W| 3 2. An example is a star
graph S of order p > 3. Then 81L(S) = 81U(S) = l and S
has p-Z weak vertices.

If P is a path. then IPI denotes the length of this
path, i.e. the number of edges in the path. We need the
following three definitions.

qr-

”m“-
-
73-

16

Definition 3,1. Let G be a connected graph and M a matching

of G. Then two edges e1 and e2 in M are said to be ppgg to
one another if there exist a path P in G containing e1 and
e2 such that |P| 5 4.

It is clear that for such a path P, either IPI = 3 or

IPI = 4, since edges in M are disjoint.

Definition 3 2. If G is a connected graph and M is a

 

matching of G, then the matching M is said to have property
(P) if for any two near edges e1, e2 in M, a shortest path
P(e1,e2) containing e1 and e2 has exactly one weak vertex

between e1 and e2.

Dgfinigion 3.3. If G is a disconnected graph, and if M is
a matching of G, then M is said to have property (21 in G,
provided the matching induced by M in each component of G
has property (P). In the trivial case wherel MI = 1, we

agree that M has property (P).

Ingppgm I2. Let G be a connected graph and M a matching
of G. If IMI 3 2, then there exist at least one pair of
near edges in M.

2:99;: If there exist a path P containing two edges
in M such thatl PI 5 4, then the theorem follows at once.

Hence, we may assume that the length of every path in G

 

.u— .v‘.“_,

17

containing two arbitrary edges of M is always 3 5. Let P

be the shortest such path, say P 1 v1, v2, . . . , VK’

where K 3 6. Then we conclude that v3, v4, . . . , vK_2
are all weak vertices relative to M. If there were a neutral
vertex. say Vi' 3 5 i 5 K-Z, then by definition V1 is in-

cident with a strong edge (vi,u). The path P's u, Vi’ Vi+l,

. . . , VK_1. vK contains two edges of M, but IP'|< IPI,
contradicting the assumption that P is the shortest such
path. But if v3, v4, . . . , VK-Z' are all weak vertices
where K 3 6, then M is not a matching, a contradiction.
Hence, we conclude there must exist at least one pair of

near edges in M.

Theppgm 3,3. Let G be a connected graph. A matching M has
property (P) if and only if every shortest path P(e1,e2)
containing any two near edges e1 and e2 of M has length
four and exactly one weak vertex between e1 and e2.

1 gpppfi Since e1 and ez are near edges in M, there
exists a path P containing e1 and e2 such that |P| 5 4.
The shortest path P(e1,e2) containing e1 and e2 then sat-
isfies |P(e1,e2)| 5| Pl 5 4. Since e1 and e2 are disjoint
edges, 3 5 |P(e1.e2)l 5 4. If |P(e1,e2)l = 3, then
P(e1,e2) has no weak vertex between e1 and e2, contradicting
the assumption that M has property (P). Therefore

IP(e1,e2)I = 4 and P(e1,e2) contains a vertex v which is

 

18

not an end vertex of elor e2. If v is not a weak vertex,
then v must be a neutral vertex and adjacent with an edge
e = (u,v) in M. In this case e1 and e and also e2 and e
are pair of near edges in M, and |P(e,e1)l = 3,
|P(e,e2)l = 3, again contradicting the fact that the matching
M has property (P). Therefore v is a weak vertex, and the
theorem follows.

The converse is clear, since this is merely the defini-

tion of property (P)

In order to obtain one of our main results (Theorem 3.4.)

we first prove two lemmas.

Lgppp 3.1. Let G be a connected graph and M a matching of
G having property (P). If v is any weak vertex relative to
M, then M has property (P) in G-v.
ngpfa We first show that the subgraph G-v has no
isolated vertex. Suppose that there exists an isolated
vertex v0 in G-v. Then V0 is clearly adjacent only to v in
G, and since v is a weak vertex then v0 is also a weak vertex.
This contradicts the fact that M is a matching. since no
matching permits adjacent weak vertices.
Next, consider the following two cases which arise
when v is any weak vertex relative to M.

Caps (1). If v is a cut-vertex of G, then G-v is

 

(.0-

l9

disconnected and consists of L 3 2 components C1, C2, . .

O ’ CL.

the component Ci' has property (P) for i = 1, 2, . . . , L.

We claim that M/C , the matching induced by M on
i

If IM/Ci| 3 2. Let e1, e2 be two near edges in M/Ci'
therefore these are also two near edges in M. Let P(e1,e2)
be a shortest path in Ci containing e1 and e2. Since
|P(e1,e2)l 5 4 in Ci’ then ‘ P(e1,e2)I = 4, since the
supposition that |P(e1,e2)| = 3 contradicts the fact that
M has property (P). By Theorem 3.3, M/C has property (P)
i
in Ci' for each i = 1, 2, . . . , L, so M has property (P)
in G‘V- For the case M/C = 1,the result is clear.
1

Case (ii). If v is not a cut-vertex of G, then G-v is
connected. Let e1 and e2 be any two near edges in M, and
P(e1,e2) a shortest path in G-v containing e1 and e2, as in
Case (i), |P(e1,e2)l = 4. Theorem 3.3 again shows that M

has property (P) in G-v.

Lgppp_§;2. Let G be a connected graph and M any edge
matching in G. If v is not a cut-vertex in G, then there
exist a matching M in G-v such that eitherl Ml = IM |or
|fil=IMI-1.

2:99;: We consider two different cases, depending on
the degree of vertex v.

gage ( I. v is an end vertex of G. Let v be incident

with the edge e = (u,v). (a) If v is a weak vertex, then

— vvv'

20

M is also a matching in G-v. Setting M = M, we have
IMI =| Ml. (b) If edge e is in M, and M-e is a matching
in G-v, set M = M-e, then IMI = IMI - 1. However, if M-e
is not a matching in G-v, then there exist at least one weak
vertex w adjacent to u, otherwise if all vertices adjacent
to u were neutral, then M-e would be a matching in G-v.
Now set M = M - e + (u,w). It is clear M is a matching in
G-v, and |fil=|Ml- 1+1=|M|.
Case ii . v is not an end vertex of G. (a) Suppose
that v is a weak vertex relative to M. Then M is also a
1 matching in G-v. Setting M = M, we have IM |= |MI .
(b) Suppose that v is a neutral vertex, so that v is in-
cident with an edge e = (u,v) in M. If M - e is a matching
‘ in G-v, set M = M - e, so that IMI = IMI - 1. If M — e is
i not a matching for G-v. then there exists at least one weak
vertex w adjacent to u, otherwise if all vertices adjacent
to u were neutral then M - e would be a matching in G-v.
Again set M = M - e + (u,w). Then M is a matching in G-v,
because no two adjacent weak vertices exist in G-v. In

' this case IMI: IMI.

Repgpk: This lemma may happen to hold even when v is
' a cut-vertex, but in general the assumption that v is not
a cut-vertex is essential. For example, if v is the center

of a star graph, this lemma fails to hold true.

 

A

I. SivsP.

21

The next theorem gives a sufficient condition for a
matching to be a minimum matching. It is assumed that the

graph G has no isolated vertices.

Theorem 3,4. Let G be a graph which possesses a matching
M having property (P). Then M is a minimum matching.

Egppfs We will use induction on the order of G.
Assume that for any graph G0 having order less than that
of G then the theorem is true, i.e. if M0 is a matching
of G0 having property (P) then M0 is a minimum matching
for G.

If G is not connected. then by definition 3.3 the
matching induced by M on each component has property (P)
provided M has property (P), so by the inductive hypothesis
such induced matchings on each component are minimum
matchings. Thus M is a minimum matching for G, since the
matching for any two components are disjoint.

We henceforth assume that G is connected. If IMI = 1,
the theorem is trivial. We may therefore assume |M| 3 2.
This assumption. together with the fact that M has property
(P) implies the existence of weak vertices in G relative to
M. Let us assume that M is not a minimum matching, and
seek a contradiction. Then there exists a matching M in
G such that IMI < IMI. There are two cases to consider.

Cage (12. There exists at least one weak vertex

22

(relative to M) which is not a cut-vertex of G. Now M is
obviously a matching in G-v, and by Lemma 3.1, M has
property (P) in G-v. By induction, M is a minimum matching
in G-v. Next consider M in G. Since v is not a cut-vertex,
by Lemma 3.2, there exists a matching M* in G-v such that
either IM*I = I MI or I M*I = I MI - 1. Since M is a minimum
matching in G-v, we have IM*I 3 H41. Ifl M*I = I fil then

IMI 3| MI, a contradiction. If |M*| =| MI - 1, then

IMI - 1 3| MI. and IMI >| Ml, again a contradiction. Thus
no such matching M can exist. so in case (i), M is a
minimum matching.

Case 1 . All weak vertices (relative to M) are cut-
vertices of G. Difficulties arise if a cut-vertex of G is
removed, since the resulting graph G-v might have isolated
vertices, and in this case no matching for G-v is possible.
In order to make use of the inductive hypothesis, we resort
to a shrinking process applied to suitable subgraph of G.
When a subgraph A is shrunk to a vertex v of A, we mean that
the entire graph A is replaced by the single vertex v.

Let v be a weak vertex and A0 any component of G-v.

Set A = <AOU {v}> and let GA be the graph constructed from
G by shrinking the (block) A into the single vertex v. We
show first that the matching M induces matchings on A and

on GA both of which have property (P). Denote by M(A) and
M(GA) the matchings of A and GA induced by M. If |M(A)| = 1

A

23

or IM(GA)| = 1, the resulting induced matching is clearly
a minimum matching. Therefore we assume that IM(A)I: 2
and IM(GA)| 3 2. To show that M(A) has property (P) in A,
let e1, e2 be any two near edges in M(A), and P(e1.e2) a
shortest path containing e1 and e2. It is clear that
IP(e1,e2)I5 4. Also since e1 and e2 are two near edges in
M, by theorem 3.3, we know that I P(el,e2)I = 4 and that
P(e1,e2) has exactly one weak vertex between e1 and e2.
Similarly M(GA) has property (P) in GA' Therefore by
induction M(A) and M(GA) are minimum matchings of A and GA'
respectively.

Now consider the following two cases:

Case (iia). The vertex v is a weak vertex with respect
to M, then M(A) and M(GA) are matchings for A and GA
respectively. Since M(A) and M(GA) are minimum matchings
of A and GA respectively, we have IM(A)I 3 IM(A)I and
IM(GAH 3| M(GA)I. Then Ifil=|fi(A)I +|fi(GA)I 2|M(A)l
+ IM(GA)| =I MI, a contradiction.

Ca e iib . The vertex v is not a weak vertex with
respect to M. If M(A) and M(GA) are matchings for A and
GA respectively, then by the same argument employed in
case (iia) we obtain IMI 3| MI, a contradiction. Hence
we may assume either M(A) is a matching for A, or M(GA) is
a matching for GA' for they cannot both fail to be matchings

for A and GA at the same time, otherwise M would not be a

pfi—g _._____

24

matching. Let us assume M(A) is a matching and M(GA) is
not a matching, this could happen only when v is a weak
vertex relative to M(GA) and there are weak vertices
relative to M(GA) adjacent to v. However M(GA) is a
matching for GA-v. Now, consider M(GA) in G . Since v is
a weak vertex with respect to M, and also a weak vertex
with respect to M(GA), and M(GA) has property (P) in GA'
then by lemma 3.1, M(GA) has property (P) in GA-v. By
induction M(GA) is a minimum matching in Ga-v. Hence
Ifi(GA)I Z IM(GA)|. Also since I M(A)I 2 IM(A)I. then
Ifil=lfi(A)I +Ifi(GA)I zIM(A)I + IM(GAH =|MI. again a
contradiction. Hence we conclude that M is a minimum

matching in G.

Section 3.2. Weinstein [25] in 1961 determined a non-
trivial lower bounds for BlU(G) in terms of the maximum
degree A(G) of G, depending on the value of the minimum
degree 6(6). (1) For 6(6) 3 1. |v(G)I s (1+A(G))'81U(G)
(2) For 6(G) 3 2, 2Iv(6)| _<_ (2+max(4,A))'Bw(G)

In this section, we obtain non-trivial lower bounds for
BlL(G)’ in terms of A(G) and show that these bounds can be
attained, so are sharp.

We first establish a lower bound for 81L(G) in the

case that G is a tree.

 

 

25

Theorem 3.5. Let T be a tree of order p, and maximum
degree A(T). Then p 5 2 A(T)-81L(T).

2:99;: We use induction on the number of edge of T.
Suppose T0 is a tree with IE(TO)| < IE(T)I, we assume that
Iv(I0)|.5 21>(To)81L(IO), and shall prove that
p s 215(I)-31L(T).

Let M be a minimum matching for T, i.e. IM I= $1L(T).
If there are no weak edges in T relative to M, then all
edges of T are in M. Since T is connected, this is possible
only when T 8 K2. In this trivial case, the theorem
follows easily.

Hence, we assume there exist weak edges in T relative
to M. Consider the following two cases:

Case (1). There exists at least one weak edge e,
which is not an end edge. Consider T' B T - e, it is clear
M is also a matching in T', with IV(T')I = IV(T)I. Since
every edge of a tree is a bridge, then T' is a forest.
Consider the components C1, C2, . . . , Cn of the forest T';

by induction we have IV(Ci)I 5 215(Ci)-81L(Ci). Hence

n n
p = IV(T')I = slv<c )I 5 2 z 15(c )-s (c )
i=1 1 i=1 1 1L i

n
2A(1:')-i§1 BlL(Ci) 5 2A(T)-I31L(T)

IA

Case (ii). A11 weak edges of T relative to M are end

edges. We claim first that T is a tree with diameter 5 3.

26

Let the path P(u1.u2, . . . . uK) be a diameter of T if

IPI 3 4, then K> _5, it is clear the edges (u2.u3), (U3,U4),
. . . , (UK-Z'uK-l) are not end edges and it is impossible
for all these edges to be in M, since M is an independent
set of edges, hence there is some edge which is not an end
edge. This contradict the assumption. Therefore T is a
tree of diameter 5 3, i.e. T is a union of two star graphs,
joined by an edge between two centers of the stars. It is
clear in this case I M |= 1. Suppose the degree of these
center vertices are <11 and d2 respectively. we may assume
l_<_d15d2 that is A(T)=d2, NowlTl=d1+d2 and
31L(T) = l and p = (11 + d2 5 2 0 d2 = 215(T)'81L(T).

Ipepzpm 3.6. Let G be any graph of order p with maximum
degree A(G), and having no isolated vertices. Then
1: _<_ 2A<c)-91L(c).

3:99;: We use induction on the number of edges.
Suppose H is a graph having no isolated vertices and
IE(H)| < |E(G)| . We assume IV(H)I 5 2A(H)'81L(H) and we
shall show that p5 2A(G) 81L(G).

If G is not connected. let C1.C2, . . . , CK be the

components of G. By induction on each component we have

|V(Ci )|_<_ 2A(Ci )' :1L(Ci ), i. :3 112. a u o p K. Then
K K
p '1§1IV(C1)I $2 i§1 Kimc ) 811L(C )5 <-z:2A(G) élalei)
s man-Bum)

 

27

We now assume that G is connected. If G is a tree, our
result follows by theorem 3.5. We may therefore assume that

G is not a tree. Then there exist a cycle C in G. Let M

be a minimum matching for G. Then there exists in C at

least one edge e such that e is a weak edge with respect

to M. Now set H = G - e. We have 6(H) 3 1 and [i(H) 5 [5(G),
moreover M is a matching in H. Hence 81L(H) 5 IMI, now

IV(G)I = I V(H)I = p and |E(H)| < |E(G)I. By induction,

we have p < 2A(H)'BIL(H) and

p s ZA(H)-81L(H) s 2A(G)-|MI -= 2~A(G)'81L(G).

Remark: For each j 3 1 there exists a graph G with
A(G) = j, 6(6) 1 and IV(G)| = 2-A(G)°81L(G).
For example, let G be a tree of diameter = 3, as in
the prove of theorem 3.5. Set IG |= 2n, and deg u = deg v = n,

81L(G) . 1 then 2n = 2. A(G)°BIL(G) = 2-n-l.

 

“ 'un-l

vn-l

Figure 3.2. A graph illustrating a sharp lower bound
when 5(6) 3 1.

Hence the inequality stated in theorem 3.6. is a best

28

possible result, in the sense that equality can be attained.
However, our lower bound for 81L(G) in some examples may
be poor.

In this section our principal result (Theorem 3.7.) is
an analogue of theorem 3.6, but provides a sharper lower
bound for 81L(G) when the minimum degree 6(G) 3 2, namely
IV(G)I _<_ (l +A(G))'BIL(G). In proving this result we shall

use the following lemmas.

Lgmma 3.3. Let Cn be a cycle of length n. Then BlL(Cn) ={n/3}.
In this lemma, {x} denotes the smallest integer not less
than x.

Proof: Consider the following three cases, where
n 8 3K, n = 3K +-l or 3K +'2, and K = l, 2, 3, . . ..

Cage (i). If n = 3K, then C3K={v1, v2, . . .. v3K}
is a cycle of length 3K, construct a matching M as follows
M = {(v2,v3), (5,v6), . . ., (v3K_1, V3K)}' M clearly has
property (P), hence by theorem 3.4. M is a minimum matching,
andIMI l3 {/3}.

., V3K' V3K+1} is a cycle of length 3K + 1. Construct a
matching M as fOIIOWS M 3 I (V19V2)o (V40V5)9 - c or (V3K-29
V3K-1)' (V3K' V3K+l)}' | M |= K +'1. We cannot employ
theorem 3.4, since M does not have property (P). However

if M.were not a minimum matching, then there exists a

29

matching M*, such that I M*| <|MI -—- K + 1, then IM*I 5 K.
Hence there are at least K+1 weak vertices relative to M*.
This implies there exist two consecutive weak vertices in
C3K+l relative to M*, which contradicts the fact that M*
is a matching. Therefore M is a minimum matching and

m . =- x +1 = (WU/3} - {”3}-

Cage (iii). If n = 3K+2, then C3K+2 =‘Iv1, v2, . . .
., V3K+1’ V3K+2I‘ isla cycle of length 3K+2. Construct a

matching M as in case (ii). If M were not a minimum
matching then there existsa matching M*, such that

IM*I < IMI. This will imply that there exists a matching M
in 0310+,1 such thatI M I5| M |= K + l, which contradicts the
fact that a minimum matching of C3K+l is of order K+1.

Then I M I= K + 1 = I<3K+2)/3} =*{n/3}.

Hence we conclude that in all three cases 81L(Cn) =‘In/3}.

Lgmma 3.4. Let G be a connected graph, and M a matching of
G. Let X and Y be subsets of V(G), such that they form a
partition of V(G), i.e. XUY = V(G) and my =4. Let H
and K be any graphs (not necessarily subgraphs of G) having
vertex sets X and Y respectively, such that A(H) 5 A(G)
and A(K) 5 A(G). If M1 and M2 are matchings for H and K
respectively with I M1 | + | MZI 5 I MI, and in H and K we
have the inequalities | X |==IV(H)| 5 (1 +ZSCH))- M1_I Y I
= IV(K)| 5 (l + A(K)) M2 , then in G we have IV(G)I 5

(1 + A (G))-|M I.

30

Ppppf: The proof is trivial, since
IV(G)I = IV(H)I +IV(K)I 5 (1 +A(H))°IM1I + (l +A(K))-|M2I
5(1 +A(G))-(IM1I + IMZI) = (1 +A(G))'IMI.

Theozem 3.7. Let G be a graph of order p with 6(6) 3,2.
Then p 5 (1 +A(G))-BIL(G).

2299;: We use induction on the edge numberl E(G)Iof
G, and assume that whenever H is a graph with 6(H) a 2 and
IE(H)| < IE(G)| then IV(H)| 5 (l +A(H))°81L(H). We
shall show that p 5 (1 +A(6))-31L(6). Throughout the
entire proof of this theorem, we will let M be a minimum
matching for G. If G is not connected, let Cl' 02’ . . .. CK
be the components of G and M/C , i = 1, 2, . . .. K the
matching in C1 induced by the matching M. Then
IM/C I = BlL(Ci)' By using induction on each component, we
have1IV(Ci)IS(1 + A(Ci))-81L(ci). i = l, 2, . . .. K.
Then

K K
p =i§I1V(Ci)I $1510 + A(Ci))-BIL(Ci)

K
_<_ (1 + A<G>>1§§1Lw1> = (1 + A(G))~31L(G)

We next assume that G is connected, and define
S ={vEV(G)I deg v 3 3}. T ={v€V(G)I deg v = 2}. we
first note that we may assume that S #4), for if S =¢ ,

since G is connected then G is a cycle and by lemma 3.3.

31

sum) = {W3}. Now (1 + men-sum) = 3|P/3} z{3-P/3} = p.
so the theorem holds in this case.

We may also assume that T #4), for if T =4) , then
there exist two 3 - vertices joined by a weak edge e = (u,v).
Setting H a G - {e}, we have 6(H) 3’2 and IE(H)| < |E(G)l.
Hence by induction IV(H)I 5 (l + £i(H))'BlL(H). But since
M is also a matching of H, we have I M l3'81L(H). Also
since p = IV(H)I, we obtain p 5 (l +AA(H))-BIL(H)
(1 +A(G))°81L(G), and

IA

again the theorem follows.

Note in the above discussion of the case where T #4)
we have also shown that the graph GIS is either discrete
(i.e. totally disconnected) or joined by edges in M,
between 8 vertices.

Now we are going to prove the theorem in the following
five steps in the case where S #4) and T #4) .

(1) Let P be a path between two 3 - vertices. If the
terminal edges of P are weak edges the theorem follows if
IPI > 2, so we may assume I P I5 2.

(2) The theorem follows when GIS is not discrete (i.e.
totally disconnected), so we may assume that GIS is discrete.

(3) If there exists an edge in M which is not incident
with an S - vertex, the theorem follows. Therefore we may
assume that all edges in M are incident with S - vertices.

(4) For any path P between two S - vertices, the

32

theorem follows whenI P I5 4.
(5) If the assumptionsmade in steps 1-4 hold. Then
Is I = I M land A(G)-ISI 3 III.
After proving these five steps, the proof of the
theorem will be immediate, since ISI +I TI 8 p.
Now A(G)-Isl 3|TI = p -IsI.
(A(G) + 1 )-ISI 2 p. but sincel s I=I MI- sum).
Therefore we conclude (1 +ZS(G)).BIL(G) 3 p.
(1) Let P be a path between two S vertices x and y say,
and the terminal edges of P are weak andI P I> 2.
Cape g 2. X = y
Lil—'12- Degx=desyi4.
Set H a P(u, “1' . . .. v), and K = G - V(H). Since
5(3) 3 1, by theorem 3.5. we have IV(H)I 5 2A(H)-31L(H) =-
4-81L(H) 5 (l +A(G))-81L(H), and in K we have 6(K) 3 2
and IE(K)| < IE(G)I. By induction we have
IV(K)I 5 (1+ A(K))-81L(K). Let M(H) and M(K) be the
matchings on H and K induced by M, then we have
IM(H)I 3 BlL(H) and IM(K)I 3 81L(K). Thus by lemma 3.4.
the theorem follows.
M. Deg x 8 deg y - 3, let us trace the path
P(x, x1. . . .. xN) to the nearest 8 vertex xN, since (u,x)
and (v,x) are weak edges, the first neutral vertex on the
path P(start from x) must be either x - y, or x1. Also we

note that there must exist a T vertex w adjacent to xN,

33

for if all vertices adjacent to xN are S vertices, this
implies that there are weak edges joining two S vertices,

which contradicts our assumption.

 

Figure 3.3. Existence of a T vertex w adjacent to xN.

If x = y were the first neutral vertex, we can set

H = P(u, ul. . . ., v), and K = G - V(H) +-(x,w). In H by
2-A(H)-31L(H) = 4-81L(H)

(1 +A(G))-BIL(H).

In K we have 6(K) 3_2, IE(K)I < IE(G)I and

[5(K) 5_£§(G). By induction we have IV(K)I 5,(l +23CK))-
81L(K). Let M(H) and M(K) be the matchings on H and K

theorem 3.5. we have IV(H)I 5
<

induced by M, then we have IM(H)I 3 BlL(H) and

IM(K)| 3 81L(K). Thus by lemma 3.4. the theorem follows.

If x1 were the first neutral vertex we can set

H - C(x, u, . . .. v, x) and K - G - V(H) + (w,x1).

Similarly, by induction and lemma 3.4. the theorem follows.
Cape ( 2. x f y. Set H - P(u, “1' . . ., v) and

K = G - V(H). In H, theorem 3.5. implies IV(H)I 5 213(H)'

Bum) S. (1 +A(G))'31L(H)

34

In K, we have 6(K) 3 2. IE(K)I < IE(G)| and 1300 _<_ A(G).
Again by lemma 3.4. the theorem follows. Therefore we may
assume thatI PI = 2.

(2) GIS is not discrete. We have shown that if
GIS is not discrete, then there are only strong edges joined
between vertices in S. If there exist two 8 vertices x and
y, joined by a strong edge (x,y), then by step (1) any path
between x and y has length 2.

Figure 3.4. Two S vertices x and y joined by a
strong edge.

Set deg x = N + 1, deg y = L + I. We may assume without
loss of generality that N 3:L. Now, let us consider the
following various of cases.

Cas -.a. N=L=O. Then 132, we have
A(G) =- I + 1, p = I + 2 and BIL(G) ‘ 1, then
p = I + 2 = (A(G) + l)°BlL(G), thus the theorem follows.

35

Case -b. N = l, L = 0, and I 3_2. Let us trace the
path P(x, x1, x2, . . ., xR) to the nearest S vertex xR, we
have R 3 2, by the same argument as in step (1) case (a-Z)
there exists a T vertex w adjacent to x . Now consider the
following two possibilities, start from x in the path P.
Either x1 is the first neutral vertex or x2 is the first
neutral vertex. If x1 were the first neutral vertex, set
H g G/<x' y. v1, . . .’ VI) and K = G - V(H) + (x1,w). In
H we have IV(H)I = I + 2 = (l +23(H))-BIL(H). In K we have
6(K) 3 2. IE(K)| < IE(G)|, by induction IV(K)I g (1 +13(K))'
81L(K). Similar argument as before the theorem follows by
lemma 3.4. If x2 were the first neutral vertex, we can set

_ G
H l<x10 xv Y: V10 0 o 00 VI
K = 6 - V(H) + (x2,w) if R > 2. In H we have IV(H)I = I + 3

> and K = G - V(H) if R = 2.

and I + 3 = (l + (I + 2))'l = (1 +A(H))°81L(H). Again in K
by induction we have IV(K)I 5 (l +25(K))081L(K). From lemma
4.3. the theorem follows.

Ca -c. N 3_2, L = 0 and 1 3,2. We divide the set
of vertices-{x1, x2, . . .. KN} into two sets, namely M(x) of
those vertices incident with edges in M, and M'(x) of those
vertices not incident with edges in M. Set H = G/

(Y! V10 0 o
. .' vI' x and xi£M1(x) > and K = G - V(H). In H we have
IV(H)I = I + 2 +IM'(x)|. NR) = I +IM'(x)I+ 1. sum) = 1.
Thereforel‘V(H)I = I +-2 +-IM'(x)I = ((I +~IM'(x)I + l) +

1)-l = (l +A(H))'81L(H).

36

As for K, we are going to construct a graph K from K, such
that IV(K)I = I V(K)I , 6(K) 3 2 and A(K) 5A(G). Moreover
there exists a matching M* in K such that IM*I =I MI - 1.

If in K we set M* = M/E (i.e. M* is the matching induced

by M on K), then for x1€M(x), the x1 are strong vertices
relative to M* and are of degree one in K. As for the ver-
tices z's joined to xiéMf(x), they are either neutral or
strong vertices relative to Mk depending upon whether their
degree > 1 or = 1. Now, we can construct K from K by joining
the xi's in M(x) and the 2's of degree 1, among themselves in
pairs if they are even in number. If the number is odd the
extra vertex can be joined to a T - vertex, so thatz§(K) 5
21(6). 600 z 2 and IV(K)I == IV(K)I. It is clear by the
construction that M* is a matching of K andI M*I =I MI - 1,
hence by induction we have IV(K)I 5 (1 +A(K))-81L(K).

Thus by lemma 3.4. the theorem follows.

Ca -c. N 3 L 3_1. We first establish that we may
assume there exists a T vertex incident with an edge in M.
For if there were no I vertex incident with an edge in M
thenI MI = ISI/2. To verify this statement, it is clear that
since M is incident only with S vertices (as will be proved
in step 3 on page 39), then IMI$,IS|/Z. Conversely if there
exists an S vertex, say so. not incident with edges in M, then
one of the vertices joined to so, say 3, must be a neutral

vertex. If deg s 3_3, then we have two S vertices joined by

37

a weak edge. If deg s = 2, this contradicts our assumption.
Hence 2 IMI 3 ISI, i.e. I M I= ISI/2. Now count the number
of edges in G. Since the path between two adjacent S ver-

tices is either an edge in M or two weak edges we have

q = 2; deg s - ISI/23 ZITI +|Sl/2.
5% S
and A-ISI - ISI/2 3 2m +IS'/2.

ZS-Isl 3 2|TI +-IsI = 2p -I sl.
I3|.(A+ 1) 3 2p. '3'/2-(A+ 1) =IMI -(A+ 1) 3 p.
Therefore the theorem follows. Thus we may assume that

there exist T vertices incident with edges in M.

G
(X1. X. Y! V1, 0 o 0' VI)

G/

(X: Y! V10 0 o as VI>

N = L = l and 21 # ul, set H =

or

depending on whether 21 or x1 is a neutral vertex. Then

K = G - V(H) + (zl,y1) or K = G - V(H) +~(x1,y1), and the
theorem follows by lemma 3.4. If N = L = 1 and 21 = “1'

if (x1,zl) in M or similarly (y1,zl) in M.

Set a s G)<x' y. v1. . . ., VI’ and K = G - V(H) + (x1,y1).
The result is clear. If both x1 and y1 are weak vertices

8 G
set H /<x1! X, Y! V10 0 . so VI)

(y1,w), where w is a neutral T vertex, we have established

and K = G - V(H) +

the existence of such a vertex at the beginning of case Z-d,
therefore the theorem follows by lemma 3.4.

N 3,L > 1. We may assume all yi's are weak vertices,

for if there exists one vertex, say yo which is a neutral

38

vertex, we can join all yi's to yo, and treat the rest as in
case Z-c. i.e. Set H = Gl<y,x,v1, . . .' VI and x16 M'(x)>
and K'- G - V(H). Construct K from K by joining all yi's to
yo, then from case 2-c. the theorem follows. Thus all yi's
are weak vertices. Now set H = Gl<y,x,v1, . . .' VI’ and
xéM'(x)>' (M'(x) as in case Z-c) and K = G - V(H). Assume
there are J vertices (21, . . ., zJ) adjacent to xi's. After
removing H from G we obtain J strong or neutral vertices. and
the total degree decrease arising from these J vertices is N.
Also there are L weak vertices of degree 1 in K. Since
N 3IL, we can construct K from K by joining these two sets
of vertices in an appropriate way without increasing the
degree of K. From such a construction A00 3 2, A(K) 5A(G)
and IKII=I.KI. Moreover set M* = M/K the matching induced
by M on K. It is clear from the construction of K that
IM*I = IMI - l, and the theorem follows by lemma 3.4.

Npgg: Case Z-d also shows that no strong edge can join
an S vertex to a T vertex and then be followed by a weak 5

vertex. If it does, we can set H e Gl< and

y,x,x1€M'(x)>

K 3 G - V(H).

 

Figure 3.5. 'A T vertex joining
two S vertices.

39

The same argument as case Z-c, will prove the theorem.
(3) All edges in M are incident with S vertices. For

if there exist an edge e = (x,y) not incident with an S ver-

tex, then deg x = deg y = 2.

x y x y X Y
D V V
M fl u
' ‘ w w
Q ,' \ 4' 1.’

Figure 3.6. An edge (x,y) not incident with 8 vertices.

Capp 3- . Deg u 3 3 and deg v 3 3. Set H a (x,y)
and K 8 G - V(H).

Cape 3-b. Deg u.3 2, and deg v = 2. If v is a
weak vertex and w a neutral vertex. Set H - P(x,y,v) and
K a G - V(H) + (u,w). If v is a neutral vertex, set
H = (x,y) and K a G - V(H) + (u,w). The theorem follows
again by induction and lemma 3.4.

(4) Let P be any path between two S vertices then
IPI 5:4. For if there exists a path between two 8 vertices
of length 3’5, then such a path must contains a strong edge
disjoint from S vertices which contradicts (3).

(5) GIS is discrete, and all the paths P between 8
vertices satisfy I Pl 5 4. In particular, if the terminal
edges of P are weak edges, we havel PI 8 2. Claim ISI =I MI

40

and [i-ISI 3 ITI. We have shown in (3) that every edge of
M is incident with S vertices, hencel MI S ISI. If there
exists an S vertex, say 3, which is not incident with any
edge in M, then s is a weak vertex. Let 31 be a vertex
joined to 3. Then deg 51 = 2 (otherwise we have two S
vertices joined by a weak edge), also (81,32) is in M. If
deg 52 = 2, we contradict (3). If deg 52 3,3, again we
contradict the remark stated before (3). Therefore every S
vertex is incident with an edge of M, soI M I= ISI.

Finally, we show that ZS-ISI 3 III, let us divide the
set of vertices T into three classes of subsets. Let a be
the set of T vertices, such that a vertex is in a if it is
adjacent to two I vertices. Let B be the set of T vertices,
such that a vertex is in B if it is adjacent to one I vertex
and one S vertex. Let y be the set of T vertices, such that
a vertex is in y, if it is adjacent to two S vertices. Now
consider the number of edges q in G. We have

q = 2 deg s + IaI +IBI/2
368

also q = ZIYI+'IQI + 3IBI/2.
HenceA-ISI +Ial +|B|IZZZIYI +IaI+3|B|/2o
and A-Isl3 ZIYI +IBI.
We claim that ly I3,IaI. It is clear that IaI 5 ISI/2. for
a vertex v in a, v must be on a path P of length 4, and the

terminal edges of P are therefore strong edges. There will

41

be no other a vertex on any path joining these two terminal
8 vertices. Also we have |y| 3_ ISI/2, for if |y|< ISI/2
then 3|SI+IaI+'a'lzsq-aZIin-Ial-I-aw'lz.
3 ISI +""/2 5 2m + 3””5 < ISI + 3|'“lz.
i.e. 2|S| < lfil.

Since one edge in M can contribute at most two 8 vertices
then IB|;5 2 IMI = ZISI, which yields a contradiction.
Therefore|yl 3_IS|/2 3_|a.l and ZS'ISI 3 ZIYI + IBI
3.Ia I+ IBI + |y| = ITI. Thus we conclude thatlkISI 3:ITI

and the proof of theorem 3.7. is completed.

Section 3.3. M. J. Stewart [24], has determined the number
of edges in a maximum matching for the n-th subdivision
graph Sn(G). This number, BlU(Sn(G))' depends on

q = IE(G)I. on the parity of n, and sometimes also on the
parameter BlU(Sl(G))' Similar precise results are obtained
here for the minimum matching number 61L(Sn(G). Various
cases arise depending on the value of n modulo 3. We first
prove the following theorem for the case when n = 3K-l,
where K = 1, 2, 3, . . .. It will be observed that in this

case the value of BlL(Sn(G)) depends only on K and q.

T e 8. Let G be a connected (p,q) graph. Then
Ppppf: Let both the vertices of G and the vertices of

42

S3K_1(G) which correspond to the vertices of G be labeled
as v1, v2, . . .. vp. To each edge (vi,vj) present in G,
denote the corresponding vi-vj path of length 3K in $3K_1(G)

by Pij:( vi’ ul' ”2’ . . ., “BK-1’ vj ). Next construct a

matching M in S3K_1(G) as follows: to each path Pij in
S3K_1(G) choose the edges (u1,uz), (u4,u5), . . .. (“3K-2’
u3K-1) to be the edges in M. We are choosing for M

the middle edge in each set of three consecutive edges of

P It is obvious from the construction that M is an edge

1 .
magching in SBK—l(G)' and that each path Pij contributes
exactly K edges to M. Hence IMI== K-q. The theorem then
follows if we can show that M has property (P), since by
theorem 3.4. M is then a minimum matching. Let eo be any
edge in M and consider in M all the near edges of co.
Suppose that e1 is any one of these near edges. Two pos-
sibilities arise: Case 1. The near edges co and e1 lie on
the same path P13. It is clear from the construction of M
that IP(e0,e1)I = 4, and that there exists a weak vertex
between e0 and e1. Case 2. The near edges eo and e1 lie
on two different paths Pij and Pik' Since IP(e0,e1)| 5,4,
edges eo and e1 are two terminal edges of the paths Pij
and Pik which are in M. Again, by the construction of M,
we conclude that IP(e0,e1)I = 4, and that the vertex v1 is

the weak vertex between co and e1. (See figure 3.7.) In

each case M has property (P), soI M'Ia 81L(83K_1(G))= K-q.

Figure 3.7. A weak vertex Vi
between eO and e1.

 

Corollary: Let G be an arbitrary (p,q) graph. Then
81L(S3K-1(G)) ‘3 K'qo K = 1: 2: 3: o o o
Proof: The connected case has already been considered
in theorem 3.8. If G is not connected, let G = C1\J CZLI. .
. .LICN, where C1, . . ., CN are the noneempty components

of G, and N 3 2. Then N
BlL(S3K-l(G)) = iEIBlL(83K-1(Ci))

N
= 2 K- IE(Ci)| = K~q.
i=1

In the remaining cases when n = 3K+l or when n = 3K+3,
where K = 0, l, 2, . . . , the formulas for BlL(Sn(G)) are
somewhat more complicated than that given in theorem 2.8.
since they depend also on the.values of BlL(Sl(G)) and
81L(83(G)). Nevertheless these formulas are useful, espe-
cially when K is large.

When an edge e of G and its end vertices are replaced
by a path P of length n+1 in Sn(G), we find it convenient

to say that the edge e “contains” the n+1 edges of the path P.

To each edge (V1.Vj) in G, denote the corresponding path of

length n+1 in Sn(G) by Pij' (v1,u1,u2. . . ., un,vj). For

44

instance the corresponding path of length 2 in 81(G) is

P13: (v1, ul, VJ).

Theprem 3,9. Let G be a connected (p,q) graph. Then
81L(83K+1(G)) a 81L(81(G)) + K‘Q- K = 0! 1! 29 0 O o
Prppf: Let IMOI = m denote the number of edges in a

minimum matching of 81(6), so BlL(Sl(G)) = m. Then there

are exactly m edges of G which contain an edge of Mo, and

q-m edges of G which do not contain an edge of M0.

Let both the vertices of G and the vertices of 83K+1(G)
which correspond to the vertices of G be labeled v1, v2, . .
. .. vp. To each edge (v1,vj) in G denote the corresponding
vi-vJ path of length 3K+2 in S3K+1(G) by P13: (v1, ul, uz. .
. ., u3K+1 VJ). Now, construct a matching M in S3K+1(G)

I

in a manner we now describe. Corresponding to a path

Pij:(v1,u1,vj) in 81(G) containing an edge of MO, one of

the vertices vi and vJ must be incident to an edge in M0.

If v1 does, we choose the available K31 edges in Pij' namely

(vi,u1), (u3,u4), . . ., (“BK’U3K+1) to be in M. Cor-

responding to a path P13 in 31(G) which does not contain

an edge in M0, we choose the available K edges in P1) as

follows (u2,u3), (u5,u6), . . ., (“BK-1'u3K)' Thus

IMI = m(K+1) + (q-m)K = q.K + m.

Now claim (1) M is a matching and (2) M is a minimum

matching. It is clear that M is an independent set of edges

45

in S3K+1(G). If M is not a matching, then on some path in
S3K+1(G) there are at least two consecutive vertices which
are not incident with edges in M. This can possibly occur

only on two ends of path P.1 of S3K+1(G) which contains K

J
edges in M. If v.1,u1 are two such vertices, then v1 must

be a weak vertex relative to M0 in 81(G). However in 31(G),
Pij contains no edges in M0. Therefore Vi’ u1 in 81(6) are
two consecutive weak vertices, contradicting the fact that
M0 is a matching in 81(G). Thus v1 must incident with an.
edge in M. Thus M is a matching. We next show that M is a
minimum matching in $3K+l(G)‘ If false, let M1 be a minimum
matching of 83K+1(G), and |M1I< IMI. We can obtain another
matching M2 from MI having the same cardinality as M1 in

the following way. The edges of M1 are distributed among
the q-path of S3K+1(G). It is clear that no path Pij
contains K+3 edges in M1, since M1 is a minimum matching.

If there exists a path Pij containing K+2 edges of M1, then
there must exist a path P11 or ij containing K edges of M1,
since if all paths adjacent to Pij contain K+l edges of M1,
we can construct a new matching with fewer edges than M1.
This contradicts the assumption that M1 is a minimum matching.
We can therefore rearrange the edges in M1 so that both Pij
and P11 (or ij) contain K+l edges of M1. We may then
assume that among these paths there are s which contain K+l

edges in M1, while the other qes paths each contain only K

46

edges of M1. Whenever a path Pij' contain K edges of M1,
both v1 and vj must be incident with edges of M1 not in
P13. For a path Pij containing K+l edges of M1, at most
one of v1 and Vj can be incident with an edge of M1 not in
Pij’ since otherwise K edges could be used in M1 for that
path Pij' contradicting the minimality of M1. This set of
K+l edges in M1 can be replaced by a set of K+l edges which
form a matching for Pij’ such that exactly one of v1 and vj
is incident with an edge of M1 in Pij' If this latter set
is distinct from the former, we obtain a minimal matching
having the same cardinality as M1. Repeating this process
for every path Pij containing K+l edges of M1, we obtain a
matching M2, where IMZI = I MII . We observe that M2 has the
property that a path P13 contain K.edges of M2 if and only
if both vi amd vj are incident with edges of M2 not in Pij’
and a path Pij contains K+l edges of M2 if and only if
exactly one of V1 and vj is incident with an edge of M2 in
P11. Now we choose a new independent set of edges M5 in
31(6) in the following way: corresponding to a s-path P13
containing K+l edges of M2, we choose the edge (v1,u1) or
(u1,vj) to be in M* depending upon whether v1 or vJ is in-
cident with an edge of M2 in Pij' It is clear that M* is an
independent set of edges, and we claim it is a matching for

81(6). If not then there exists at least two consecutive

vertices in 81(6) which.are not incident with edges in M*,

47

say v1 and ul. Then the path Pij contains only K edges in
M2, otherwise u1 would be incident with an edge in M*. This
implies that both vi and vj must be incident with edges of M2
not in Pij' If V1 is incident with an edge of M2 in path
Pik' then the path Pik contains K+l edges of M2. By the
construction of M*, vi would be incident with an edge in M*,
contradicting the assumption. Hence we conclude that M* is

a matching of 81(6), andl M*I = 8. Since M0 is a minimum
matching of 81(6), we have m,5 s. Howeverl MII = s(K+l) +
(q-s)°K = s + q.K 3;m + qu =I MI. Hence we have lMl' =I MI,

i.e. M is a minimum matching.

Cogpllapy: For any graph G of order p having q edges,
BIL(S3K+1(G)) = 81L(31(G)) + K'q. K = 0, 1, 2' . . .
Ppopf: The proof is similar to that given in the

corollary of theorem 3.8. and is omitted.

The next theorem completes our study of the minimum
matching number 81L(Sn(G)) by treating the remaining case
when n = 3K+3, K = O, l, 2. . . .

Thpppem 3.10. Let G be a connected (p,q) graph. Then
81L(S3K+3(G)) =1 BIL(S3(G)) + K’qo
Ppoof: In 83(G), for each edge (vi,vj) in G, the
corresponding path Pij' (v1,u1,u2,vj) is of length 4. A

48

matching for 83(6) then involves either one or two of the
edges in each such path. Let M0 be a minimum matching for
83(6), and let r be the number of edges of G which contain
two edges in M0. Then q-r is the number of edges of G which
contain only one edge of MO’ and IMOI = 2r + (q-r) = r+q.
Let both the vertices of G and the vertices of S3K+3(G)
corresponding to the vertices of G be labeled as v1,v2,. .
.. vp. For each edge (vi,vj) occuring in G, denote the
corresponding path of length 3K+4 in S3K+3(G) by Pij' (vi,
u1,u2.. . ., u3K+3.vj). Again the vertices between vi and
vj on Pij have been labeled in a way not showing their
dependence on i and j. Now construct a matching M for
$3K+3(G) in the following manner. Corresponding to an edge
(v1,vJ) in G which contains two edges of M0 in 83(6), at
least one of v1 and vJ or both must be incident with edges
of M0 in the path Pij of 83(6). In the former case, if vi
has this incidence property, we choose the edges (v1.u1),
(u3,u4), . . .. (“3K+Z’u3K+3) to be in M. It is to be noted
that the last edge selected was not (“3K+3'vj) but the
preceeding edge. In the latter case, we choose the edges
(vi,u1), (u3,u4), . . ., (“3K+3'vj) to be in M. Cor-
responding to an edge (v1,vJ) in G which contains only one
edge of M0 in S3(G), we observe that at least one of v1 and

v3 must be incident with an edge of Mo not in the path Pij
of S3(G), otherwise Mo would not be a matching. If v1 has

49

this incidence property, so that vi is a neutral vertex in
83(6), we can choose (u2,u3), (u5,u6), . . .. <U3K+2'“3K+3)'
Hence we have I M I = r(K+2) + (q-r)(K+l) = (r+q) + q-K

== 81L(S3(G)) + K-q-

We next show (1) M is a matching, and (2) M is a
minimum matching. For (1), it is clear that from the choice
of the edges of M that M is an independent set of edges in
S3K+3(G). If M is not a matching, then there must exists
at least two consecutive vertices in S3K+3(G) which are not
incident with edge in M. By the construction of M, this is
impossible for any path Pij containing K+2 edges of M. For
those paths Pij which contain only K+1 edges in M, this
could possibly occur only at an end vertex of the path Pij'
If vi and u1 are two consecutive such vertices on path P13,
then vi must be a weak vertex relative to M0 in S3(G), for
if not then Vi must be incident with an edge in M0. By
construction of M, this v1 must then be incident with an
edge in M in S3K+3(G), constradicting the fact that v1 is a
weak vertex relative to M. Hence v1 is a weak vertex
relative to M0. In this case vj must be incident with an
edge of Mo not in Pij’ again by the construction of M .
Since the vertex on Pij adjacent to vJ will then be a neutral
vertex relative to M, we find another contradiction. Thus
M is a matching.

To prove (2), suppose that M is not a minimum matching

50

for S3K+3(G). Let M1 be any minimum matching of S3K+3(G)

so I “1' < [M I. We can obtain another matching M2 from M1
having the same cardinality as M1 in the following way.

The edges of M1 are distributed among the q paths P13 of
S3K+3(G). Some of these paths - say 3 in number - contain
K+2 edges of M1, while the remaining q-s paths each contains
only K+l edges of M1. We will refer to the former as s-edges
and to the latter as q-s edges in G. Whenever a path Pij in
S3K+3(G) contains K+l edges of M1, at least one of v1 and

vJ must be incident with an edge of M1 not in path P1).
Whenever a path Pij contain K+2 edges of M1, we may replace
this set of K+2 edges by a set of K+2 edges of P13 which
form a matching in the subgraph P13 itself. Moreover, one
of v1 and VJ. or both, is incident with edges of M1 in Pij’
if this latter set is distinct from the former. It is
impossible for both v1 and vJ to be incident with edges of
M1 not in P13, otherwise K+1 edges could have been used in
M1 for the path Pij' contradicting the minimality of IMII.
This replacement yields a matching having the same cardi-
nality as M1. Repeating this process for every path P1)
containing K+2 edges of M1, we obtain a matching M2, where
IMZI = IMII. Next, we choose a new independent set M* in
33(6) with the assistance of M2. For a path P13 containing
K+2 edges in M

, we are going to choose from P in 83(6)

2 ij
two edges in M*, these two edges will be incident with v1 or

51

vJ depending on whether or not v1 and vj are incident with
edges of M in P1), and choose from Pij in 33(6) one edge in

M*, if the path P contains K+l edges in M2, and this edge

i
is distance two awiy from the vertex vi (i.e. from vi to
the near end vertex of this edge is distance two) or vj, if
v1 or V3 is incident with an edge of M* not in Pij' It is
clear that vi and vJ cannot both be weak vertices relative
to M2 and cannot both be incident with edges in Pij in M2.
In either case, K+2 edges are needed for Pij in order that
M2 be a matching. In case both.v1 and v3 are incident with
edges of M* not in Pij’ we can choose an edge of Pij in
53(G) distance two away from either vertex v1 or VJ. Now,
we show that M* is a matching in 83(6). If not, there
exists at least two consecutive weak vertices on Pij relative
to M* in 33(6). By the construction of M*, one of these
vertices must be a vertex vi of G. Then the corresponding
path, say P13, in $3K+3(G) is either an S-edge or a q-s
edge. If (v1,vj) were a s-edge, then VJ must be incident
with an edge in M* in P13, and there would be two strong
edges relative to M? between vi and vj. Hence consecutive
weak vertices on Pij are not possible. If (Vi’vj) were a

*
q-s edge, then vj must be incident with an edge of M not

in P Thus by the construction above, the edge chosen in

ij'
M* is distance two away from v). This makes the vertex in

Pij adjacent to v1 a neutral vertex and not a weak vertex

52

relative to M*. Hence M* is a matching and IM*I = s + q.

Since M0 is a minimum matching in 83(6) we have r+q 5 s+q,

i.e. r 5 3. Now IMlI =I MZI = s(K+2) + (q-s)(K+l)
= (SIq) + q-K SI M I

(r+q) + K'q.
Hence 8 = r, i.e. IMI = IMII.

Thus we conclude M is a minimum matching.

Corollary: Let G be any (p,q) graph. Then
81L(83K+3(G)) = 81L(83(G)) + K'q. K = 0. 1’ 2’ . . .
Progf: The proof is similar to that given in the

corollary to theorem 3.8. and is omitted.

CHAPTER 4
EDGE COVERINGS

Sectgpn 4.1. The graphs considered in this chapter are
understood to have no isolated vertices, since no edge can
cover an isolated vertex. A set C of edges of a graph G
is called an gggg covering pg; of G, provided each vertex
of G is incident with at least one edge that belongs to C.
An edge covering set C is called an edge covering (or simply
a covering) of G provided there is no edge covering set of
G which is properly contained in C. The set of all edges
of G, for example, is a covering set but ordinarily is not
a covering. The usual edge covering number a1(G) denotes
the cardinal number of a covering having the minimum
number of edges. We will designate this number by d1L(G).
In addition to the minimum covering number, we also define
the maximum covering number a1U(G) as the cardinal number
of a covering having the largest possible number of edges.
Let G be a (p,q) graph and C an arbitrary covering of
G. we denote by a =I C I the number of edges in C. It is
clear that p/Z 5 a1L(G) 5 a(G) S a1U(G) g p-l.
Since p g 2a1L(G), we also have

53

54

a1L(G) 5 a1U(G) 5 2a1L(G)-l.
If G=Kp denotes a complete graph of order p, we have
a1U(Kp) = p-l. If G is a cycle Cn or a path Pn, then
2n 2 n+1
“lu(Cn) a [ l3] and a1U(Pn) = [ ( )/3].

Theopem 4,1. Let C be any covering of a graph G of order p.
Then the number of components of <C> in G is p-ICI.

3399;: For any covering C of G, no three edges in C
can be the edges of a path of length three in G, since the
middle edge could then be omitted from C, violating the
definition of a covering. Thus the induced graph <C> must
be a union of A star subgraphs. Let vj be the center of
the j-th star subgraph, j = l, 2, . . .. 1. In case the
star subgraph is K2, it is immaterial which end vertex is
called the center. If vJ is adjacent to aj vertices in the
j-th star graph then “j is less than or equal to the degree
of V3 in G. Since C is a covering of G and covers all
vertices of G, then

A

A 1
+ 2 a1 = p.
3‘1

If a is the edge covering number of C, then

A
a=z «1 =|Cl.
J=1 3

and l + a = p, or x = p-a = p-ICI.

If we choose one edge from each components of C, this
set of edges constitutes a matching set M for G, but is not
necessary a matching. Then l=IMI, and we at once have the

following result, which is a variation of Gallai's theorem.

Copollary: Corresponding to every covering C of G, there

exists a matching set M of G such that ICI +-IMI = IV(G)I.

Let K(p1,p2, . . .. pj) denote a complete j-partite
graph with j-pairwise disjoint sets of vertices containing
p1. p2. . .. pJ vertices respectively, the notation being

chosen so that p1 5 pz 5 . . . S Pj- Set p = j p Then
1.
i=1

by Gallai's formula and from [6].

610(K(pl.p2. . . .. 131)) = min IEp/z]. p-pj}.
we have a1L(K(p10p2! s s so 133)) g p-min{[p/2]! p-pj}'
Also it is easy to show that

J
u1U(K(p1,p2. . . .. pj)) =iizp1 = p-p1 , a result which
we now prove.

It is obvious from theorem 4.1. thatI C Idepends on A
and that IC Iattains its maximum when l attains its minimum
value. When G = K(p1. . . .. pj), the minimum number of

components a covering C can have is p1. Hence froml CI = p-A.

J
2 pi.

we have “10(K(p19 0 o 0! pj)) = p'pl =1=2

56

figgtign_&32. It is not hard to see that an edge covering

of G and the degree sequence of the vertices of a graph of
G are closely related. Consider, for example, the following
illustrations. Let G1 and G2 be graphs of order 7 with
degree sequences (5, 3, 2. 2, 2, l, l) and (6, 3, 3, 2, 2,
l, 1) respectively (see figure 4.1.)

 

Figure 4.1. The degree sequences of G1 and 62’

Here a1U(G1) = 5 and “10(62) - 6. It will therefore come
as no surprise that an upper bound for IC Ican be derived
in terms of the degree sequence of G.

Let G be a (p,q) graph with the degree sequence d1, d2,

ooospd

, where d13d2 3 . . . . 3d . Then the degree

P P
sequence has the properties (11 + l 5,p
and
P
p 5, 2 d1.
i=1

Hence it is possible to determine a unique integer k with

57
l 5,k < p such that

k k+1
2(di+1)_<_p< 2(d1+1).
i=1 i=1
A
Define a = p - k (This definition is due to Prof. B. M.

Stewart), we have the following.

Theopem 4.2. Given any graph G(p,q) with degree sequence
d1, 3,d2 3 . . . . 3 dp, then for any covering C of G we
have I0 I 5 In. (a defined as above.)

gpppg: From theorem 4.1. if C is any covering of G,

then

A
p = A +'ICI = 2 (n

j=1 j + 1).

If we suppose that the star subgraphs of <C> to have

been lebeled so that al 3,a 2 3_. . . . 3aA it follows

that aJ 5dJ for l 5,j 5,1.
A
We have p = A +I¢CI = k +ia.
Suppose A < k, then
A A k
p... 2(aj+l)5 2(dj+1)< E(dj+1).<.p.
j=l j=l j=l

A
a contradiction. Hence k 5 A and I C I 5 6..

Since in theorem 4.2. C is any covering of G, thus we

58

have derived an upper bound for any covering C of G. Also
the equality of the upper bound can be attained. Consider,
for example, the case when G consists of n copies of K2.

Then there are n components, with degree sequence d1 = d2 =
d3 = . . . = dZn = 1 we have .

n
a=zdi=n=p/2.
i=1

Section 4.3. In 1957 Norman and Rabin [18] presented a

 

necessary and sufficient condition for determining whether
or not a given edge covering is a minimum, and also provided
an algorithm for finding a minimum cover. In the case of
maximum covers, however, we have been unable to obtain
similar necessary and sufficient conditions. But, we were
able to find a sufficient condition for a covering to be a
maximum. To develop this result, we first need several

definitions.

Definition 4,1. Let X be any subset of the edge set E(G).
If P(G,X) is a path in G with the property that as one
traverses the path from one of the and vertices to the other
the successive edges are alternatively two in X and one

not in X or vice versa, then P(G,X) is called a pg-altepna-
piyp path. In the special cases where |Pl< 3, we agree to
regard paths having two consecutive edges in X or a single

edge not in X as bi-alternative paths.

59

Let G be a given graph and C a covering of G. The
vertices of G can be partitioned into two sets:

01 ==«I~vI degcv = 1}), C2 =I_v I degcv > 1}.
Here degcv (the degree of v relative to C) denotes the
number of edges of C incident with v. Evidently

2 degC v 5 IClI' and equality folds if and only if the
viEC
2

induced graph <C> has no component isomorphic to K2.

Dgfinigipn 4,2. Let C be a covering of G. We say that C
has property (2:1, if every path joining two C1 vertices is
bi-alternative.

Our main result in this section is to show that a
covering C which has property (P*) must be a maximum
covering. The converse is false. For example, consider a
graph G consisting of two star subgraphs and an edge joining
the two centers of the stars, as Shown in the figure 4.2.
The edges shown shaded clearly form a maximum cover, but the
path P: (v1, v2, v3, v4) joining two C1 vertices is not bi-

alternative.
V
4
V1 v
3

Figure 4.2. A maximum covering failing to have
property (P*).

60

Before proving the main theorem (Theorem 4.3.). we

need to establish four lemmas.

Lgmma 4,1. If a covering C of graph G has property (P*),
then no edge of G joins two C2 vertices.

2399;: Let v1,v2 6 C2' so v1 and v2 are centers of
star subgraphs of G. There exist C1 vertices. say ul, u2
joined to v1, v2 respectively. If there exists an edge
(v1,v2) in E(G), it is clear that (v1,v2) is not in C. Then
P:(u1, v1, v2, ué)would be a path joining two C1 vertices
which is not bi-alternative. This contradicts the assump-

*
tion that the covering C has property (P ).

mema 4,;. If a covering C has property (P*), then no
component of <C> is K2.

2299;: Suppose there exists a component of <C> which
is a single edge (u1,u2). Then P: (u1,u2) is a path between

two C1 vertices which is not bi-alternative.

Lemmg 4,3. If a covering C of G has property (P*), then
every C1 vertex v has degGv 5 2.

M: Let vé C1, so there is exactly one edge of C
incident to v. If degGv > 2, then there are at least two
edges in G which are not in C and |are incident to v, let

u1 and uz be the other end vertices of two such edges.

61

Three cases arise. Case 1 . Both “1’ uz, in 01' Then
P: (ul, v, uz) is a path joining two C1 vertices, which is
not bi-alternative, a contradiction.

Case (ii). Suppose u1 in C1 and u2 in C2. Then there
exists at least one C1 vertex, say w, adjacent to uz. If
:11 f w, then the path P: (w, uz, v, “1) between two C1
vertices is not bi-alternative. If u1 = w, then P: (ul, ”2'
v) between two C1 vertices is not bi-alternative, again a
contradiction.

Case (iii). Both ul, uZ in C2, then there exists a
vertex weC1 joined to 111 (or uz). The path P: (w, ul, v)
between two C1 vertices is again not bi-alternative. Hence

we conclude that degGv 5 2.

Lemma 4,4. If C is any covering in G which has property (P*),
then for every vertex v in C2 we have deng = degGv.

2:99;: Let v be any vertex in C2, so deng > 1. If
every edge of G incident with v is in C, then deng = degGv
and the lemma follows. Thus we may assume that there exists
an edge e incident with v which is not in G. Let u be the
other end vertex of edge e. Then u cannot be a C2 vertex
by lemma 4.1. Hence u in C1. Since v is in C2, there exists
at least one C1 vertex, say w f u, joined to v. Then the
path P: (w, v, u) is not bi-alternative. But P is a path

joining two C1 vertices, contradicting the assumption

62

that C has property P*. Therefore we conclude that

degGv a degcv.

Tppppem 4,3. If C is a covering in G having property (P*),
then C is a maximum covering.

Proof: By lemma 4.2. no component of <C> is K2, so

if A is the number of components for <C>, then A = ICZI.

Also ICI = IClI = Z degcv. Let us label the vertices of
vIE'C2

C2 as v1, v2, . . ., VA and those vertices in C1 as vxfl,

VA+2’ . . ., vp. Consider the corresponding degree sequence
(in G): d1, d2. . . .. dA’ dx+l, . . .. dp. From lemma 4.4.
we know that deng1 = degGvi = d1, for l 5_i 5:A, and from
lemma 4.3. we have degij = dJ 5 2, for A+l 5 j 5 p.
By the definition of d and theorem 4.2. we have

, A

a= Edi = Zdegcv = ICI.

i=1 veC2

Since 8 is an upper bound for every covering C of G, in

this case I CI = a, C is then a maximum covering for G.

CHAPTER 5

EDGE MATCHINGS AND COVERINGS

Spgpion 5,1. In [18], Norman and Rabin discussed relations
between minimum edge coverings and maximum edge matchings.
They proved that if one begins with a minimum covering C, a
maximum matching M can be produced from it, and conversely
that from a maximum matching M one can construct a minimum
cover C. In this section we develop analogous results for
arbitrary matchings and coverings. These results generalize
Gallai's Theorem in various ways. The graphs discussed are
assumed to have no isolated vertices, so 6(G) 3_l always
holds.

In the corollary to theorem 4.1. we have proved that
corresponding to any covering C of G there exists a matching
set M of G such that I c I+| M I= I V(G) I. The first result
developed in this section is that if G is a tree a valid
result is obtained when we replace ”a matching set M" by ”a
matching M".

This modified result is not true in general, As a
counter example, consider the graph G of order 6 having a

covering C shown shaded in the figure 5.1.

63

64

Here I CI = 4, but BlL(G) = 81U(G) = 3, so far this choice
of C, there is no matching M for which I'CI +I MI = 6.

G A
Figure 5.1. A counter example.

This example shows that it is reasonable to make the

following definitions.

D i i n 5 . A graph G having the property that corre-
sponding to an arbitrary edge covering C of G, there exists

a matching M such that ICI +I M I= IV(G)I is called of

Gallai pypg pelapive pp covepings.

An analogous definition is useful for matchings.

nginition 5,2. A graph G having the property that corre-
sponding to an arbitrary edge matching M of G, there exists

a covering C such that I C I+I M I= IV(G)Iis called of
Qpllai pypg gglativp pp mapchings.

Before we prove our next theorem 5.1. we need a

65

preliminary result.

Lemma 5,1. Let T be a tree and C any covering of T. If
<C> has more than one component, then there is at least one
component Ci of <C> which is joined to the subgraph T-V(Ci)
by exactly one edge.

2399;: Let the components of C be the star graphs

C1, 02' . . . Ck' where k>l. If C is joined to T-V(C1)

l
by exactly one edge, then the lemma follows. If not, then
C1 is joined to T-V(C1) by more than one edge. Let e1 be
one of these edges. Then e1 is adjacent to some component,
say 02' If e1 is the only edge joining C2 to T-V(CZ), then
the lemma follows. Otherwise there exists another edge

e2 # el, and eZ is adjacent to a component, say 03, etc.

In this process we never encounter a component which has
already appeared in our list, since paths in a tree are
unique. Hence for i i j, C1 # Cj' Since the number of
components in <C> is finite, we must terminate our list

with a component Ci which is joined to T-V(Ci) by exactly

one edge.

ngppgm 5,1. Let T be a non-trivial tree and C any covering
of T. Then there exists a matching M of T such that
ICI+IMI=IV(I)|.

2399;: From the corollary of theorem 4.1. we know the

66

existence of a matching set M' such thatI Cl +| M'I =I TI.

Of course M' may not be a matching, but only an independent
set of edges. In the case of a tree, our problem is to
choose an appropriate edge from each component of <C> so that
the resulting set of edges constitutes a matching M. The
theorem follows at once if <C> has only one component. In
this case C = E(T), the edge set of T. Henceforth assume
that <C> has more than one component. There are then two
kind of components which may occur, namely a component which
is connected to the tree by exactly one edge (the existence
of at least one such component is proved in lemma 5.1.) and
those components of <C> which are connected to the tree by
more than one edge. Let us called the former outer compo-
nents of <C>, and the latter inner components of <C>. Each
outer component is adjacent to some component of <C> by a
single edge in T. In some cases this single edge is not
joined to the center of the star graph (type I), and in the
other case the edge is joined to the center of the star graph
(type II). If an outer component is K2, we agree that the

center is not an end vertex.

  
 

Figure 5.2. The types of

Type I
outer components.

Type 1

Type II

67

The adjoining figure shows outer components of each type.
When an outer component is removed from T, the edges of C
remaining define a cover for the resulting subtree.

A suitable matching M can now be constructed for T.
In constructing a matching, one must select one edge from
each star graph. From each outer component of type I, the
edge adjacent to the single edge joining the adjacent com-
ponent is selected. From each outer component of type II,
we choose an arbitrary edge. Next, we remove all these
outer components from T and designate these components as
belonging to level I. A new tree is obtained. The argument
is now repeated. After a finite number of steps, there will
be one or two components of <C> left. In case there is only
one component remaining, we choose any edge from it to be an
element of M. In case there are two components left, only
one edge join these components, since otherwise there would
be a cycle in T, a contradiction. Thus either component may
be regarded as an outer component. Depending on whether this
outer component is of type I or of type II, we choose a
suitable edge, and from the remaining component select an
arbitrary edge, completing the construction of M. We next
show that M is a matching for T. It is already clear that
M is a set of independent edges. If M is not a matching,

then there exists at least two adjacent weak vertices rel-

ative to M in G, say vi and VJ. These vertices cannot

68

belong to the same component of <C>, so must belong to two
distinct adjacent components, say C1 and Cj‘ The vertices
v1 and vJ cannot have degree in C greater than one. since
such vertices are neutral with respect to M. Therefore
degcv1 = l and dengj = 1. Moreover the components C1 and
C3 cannot belong to the same level of outer components,
because components on the same level are not adjacent. If
Ci and Cj were adjacent, this would imply the existence of
a cycle in T, except in the trivial case where Ci and Cj
are the only components in C. However, in this case, the
theorem follows easily by an appropriate choice of one edge
from each component. Therefore at some level one of Ci and
Cj must be an outer component, and the other an inner com-
ponent. Let C1 be the outer component, and Cj the inner.
Since dengi = 1, then v.1 is a neutral vertex relative to
M, by the manner in which M was constructed. This con-
tradicts the assumption that v1 was a weak vertex. The
proof that M is a matching in T, and that ICI +4 MI = IV(T)I

is now complete.

We conclude from definition 5.1. and from theorem 5.1.
that all trees are of Gallai type relative to coverings.
A number of sufficient conditions for a graph to be of
Gallai type relative to matchings (see definition 5.2.) will

next be developed.

69

fIhggrpm 5,2. Let G be a graph of order p with maximum
degree [5(G) = p-l. Then G is of Gallai type relative to
matchings.

gpppg: Let M be an arbitrary matching for G, and v0
be a vertex having maximum degree p-l in G. Suppose that
v0 is a weak vertex relative to M. Then V0 is the only weak
vertex relative to M, for if there exists another weak
vertex v in G, then the edge (v,vo)€E(G), and MU(v,v0) is
a matching set in G containing M, contradicting the assump-
tion that M is a matching. Thus all other vertices of G
are then neutral vertices. If u is any neutral vertex, the
edge (vo,u) is in G and the set of edges C = Ml)(v0,u) is
clearly a covering for G. Then I C I=I MI‘+ 1, so
IMI +I CI = ZIMI + l = p, proving the theorem when v0 is a
weak vertex relative to M.

Next let vO be a neutral vertex relative to M, and W
the set of edges joining V0 to all the weak vertices (rel-
ative to M) in G, and set C = MiIW. Then ICI = IM I+ IWI,
and IC I+I M I= ZIMI +I W I= p.

The restriction that 25(G) = p-l, cannot be weakened.
as the following example shows. Consider G = P4, so
p = IG I= 4 and ZA(G) = 2. There exists a matching M with
IMI = 1, and only one possible covering C, withI C I= 2.

ThenI MI'+ ICI < 4, so G is not of Gallai type relative to

70

matchings.
Tpgppgm ,3. Let G be a graph of degree p and maximum
degree A such that “111“) _ d1L(G) 2 22525-1) . Then G is a

graph of Gallai type relative to matchings.

Proof: Let M be a matching of order m. If m = BlU(G)'

 

then by Gallai's theorem there exists a covering C of order

a1L(G) such that 8111(6) + a1L(G) = p.

We may therefore assume that m < BlU(G)' or
m = BlU(G) + r, for some positive integer r. One must show

that there exists a covering C, such that IC |= a1L(G)+ r,

since then IMI + ICI = p. To show the existence of such a
covering C, by the intermediate theorem of covering [12] we

only have to show that alL(G) 5 a1L(G) +rr 5 a1U(G). By

theorem 3.6. p P P
81L(G) 2. l2 and 3111(6) " BIL(G) _<_. ,2 ' /2A

= 2£§zll . i.e. r is always bounded by

225
223-1)
151‘s 2A o
-1
Hence a1L(G) 5 61L(G) + r 5 u1L(G) + 215 5 a1U(G). and
there exists a covering C, such that ICI = a1L(G) +Ir.

Similarly we employ theorem 3.7. to prove a slightly

different version of theorem 5.3.

71

Theoggm 5,4. Let G be a graph of order p with maximum

degree A , and minimum degree 6(G) 3 2, and having

-1
«10(G) ‘ a1L(G)I3”§%§:T%. Then G is of Gallai type relative

to matchings.

2299:: Let M be a matching of order m. If m = 81U(G)
then IMI + ICI = p is an immediate consequence of Gallai's
theorem, since a cover C with ICI = a1L(G) always exists. We
henceforth assume that m < 81U(G), so m = BIU(G) - r, for
some positive integer r. We must demonstrate the existence

of a covering C such thatICI = a1L(G) +'r. By theorem 3.7.

81L(G) Z P/(1+£9 and 81U(G) - BlL(G) f P/Z _ 941+£9= 50%;1)
i.e. r is bounded by 1 5 r : g0?;1) .

-1
Then a1L(G) 5 a1L(G) + r 5,a1L(G) +-§%%;Z%5 a1U(G). By the

intermediate theorem of covering [12] there exists a covering

C, such that ICI = a1L(G) +'r, and henceI MI +I CI = p.

It is not true in general that a graph which is of
Gallai type relative to coverings is also of Gallai type
relative to matchings. Neither is it true in general that a
graph which is of Gallai type relative to matchings is also
of Gallai type relative to coverings, we present some
examples to illustrate these assertions.

Example 5.1. Let T be a tree of order 12, as shown in

72

the figure 5.3.

I * ' I
/1\

Figure 5.3. A graph not of Gallai type relative to
matchings.

By theorem 5.1. T is of Gallai type relative to coverings.
There exists a matching M of order 2, but no covering C
such that IC l+-IMI = 12. since ICI = 8. Thus T is not of
Gallai type relative to matchings.

Example 5,2. Let G be the graph of order 6 shown in

figure 5.4.

 

Figure 5.4. A graph not of Gallai type relative to
coverings.

Since 25(G) = S, by theorem 5.2. G is of Gallai type

relative to matchings. Consider a maximum cover C, for
which I cl = 5. Since sum) = 2. I M I3 2 for any matching
M, and I Cl +4 MI 3'7. Thus G is not of Gallai type relative

73

to coverings.

One might wonder if some connectivity requirement
might force a graph which is of Gallai type relative to
coverings to be of Gallai type relative to matchings, or
vice versa. We show the following counter examples, using
graphs which are blocks, that is, are Z-connected.

Example 5,3. Let G = Kp with P 3'4. Then G is a
2-connected graph and ZA(G) = p-l, so by theorem 5.2. G is
of Gallai type relative to matchings. However G is not of
Gallai type relative to coverings. As we now show, consider
a covering C of Kp consisting of all p-l edges incident with
a fixed vertex. Since BlL(G)'2 2, then for any matching M,
IMI +ch3p+l.

Example 5,4. Let G be a graph of order 14, having 6
vertices of degree 5, and 8 vertices of degree 3, as shown
in figure 5.5. We notice that G is 2-connected, it is
connected and has no cut vertices. We readily calculate the
values a1L(G) = 8, “10(6) = 10 and 81L(G) = 3, BlU(G) = 6.
Thus by the intermediate theorem for any covering C of G
there exists a matching M of G such thatI M I+I CI = 14.

For a matching M withI MI = 3, there is no covering C such
thatI CI +I Ml = 14, since 8 5I CI 5 10 for any covering
C. We conclude that G is Gallai type relative to coverings

but not of Gallai type relative to matchings.

 

 

 

 

 

Figure 5.5. A block not of Gallai type relative
to matchings.

However, we do have a characterization of graphs which

are of Gallai type relative to both matchings and coverings.

Ipengm 5,5. A necessary and sufficient condition for a
graph G or order p to be of Gallai type relative to both
matchings and coverings is that a1U(G) + BIL(G) = p.
We observe that this equation is similar to Gallai's
equation a1L(G) + BlU(G) = p.

2299;: Let G be a graph which is of Gallai type
relative both to matchings and to coverings. Consider a

minimum matching M of G for whichI M |= BIL(G). By

75

hypothesis there exists a covering C of G such that
IMI +~ICI = p. Similarly for a maximum covering 0' of G,
for which I C'I = a1U(G), there exists a matching M' of G,
such thatI M'I +-IC'I = p. Now IMI 5| M'I andl CI 5| C'I.
But inequality is impossible, becausel M I+I CI =I M'I +| C'I
= p. ThusI MI =I M'I andI C I=I C'I, so IMI +-|C'I = p.
Conversely, suppose that u1U(G) + 81L(G) = p. We seek
to prove that G is of Gallai type relative to both matchings
and coverings. By Gallai's formula, a1L(G) + 81U(G) = p.
Let M be any matching for G, so BlL(G) 5 IMI 5 31U(G).
Then p - 61U(G) 5| M I5 p - a1L(G)
or a1L(G) 5 p -I MI 5 a1U(G).
By intermediate value theorem for covering, there exists a
covering C, such thatI CI = p -I MI. i.e. IMI +I CI = p.
Similarly, let C be any covering for G, so a1L(G) 5 ICI 5
1110(6). Then p - 81U(G) _<_I c I _<_ p - 81L(G).
or 81L(G) 5 p - ICI 5 81U(G).

By intermediate value theorem for matchings, there exists a
matching M, such that IMI =p - IcI. Then IMI +IcI= p.
Thus G is of Gallai type relative to both coverings and

matchings.

Section 5.2. We again consider graphs G of order p having

 

no isolated vertices. For any matching M of G:

1 _<_ 81L(G) s I MI 5 81,,(6) s p/2.

76

The following inequalities hold for an arbitrary

covering C of G:

p/Z 5 0.1L(G) 5 I C l 5 alum) 5 p-l.
It should be observed that every number in the second se-
quence of inequalities is greater or equal to each number
in the first sequence. Clearly a covering C is also a
matching if and only ifI CI = p/Z’ so G has a l-factor.

From these inequalities we readily obtain

1 1 1 Ihi+Ich3x -1/ <3/.

Dpfinipion 5,3. For an arbitrary matching M and an arbitrary

covering C of a graph G, we define the edge Gallai ratio.

= A1(G,M.C) = IML‘I' I CI.

A
P

1
We first prove that there exist graphs G and suitable
natchings and coverings of G. such that the Gallai ratio is
arbitrary close to the upper bound 3/2. To Show this, let
G be a complete graph Kp.
Case (1). If p = 2n, then a1U(Kp) = p-l, and

81L(Kp) = n. thus alU(Kp) + 81U(Kp) = 2n - 1 +-n = 3n - l,

and alU(Kp) + BlU(Kp) 3

-1_.
p 2 2n

 

Clearly the edge Gallai ratio is arbitrary near 3/2 :for p
sufficiently large.
Case (ii). If p = 2n + 1, then alU(Kp) = 2n and

77

31U(Kp) = 81L(Kp) = n. Thus a1U(Kp) + 81U(Kp) = 3n

p 2n “I“ 1 2 + l/n

Again, it is evident that edge Gallai ratio is arbitrary

near 3/2 when p is sufficiently large.

Surprisingly, it turns out that the lower bound for
the Gallai ratio can be substantially improved. We prove

the following result.

Thepgem 5,6. Let G be a graph of order p. Then for arbi-

trary matchings M and coverings C of G, A1(G,M,C) 3 3/4, and

there exist graphsfor which this lower bound is attained.
3:99;: Suppose that there exists a graph G, a matching

M and a covering C for G, such that A1(G,M,C) < 3/4 . We

seek a contradiction. In particular, then a1L(G) + 81L(G)

< 3pl4, so we may as well assume thatI M I= 81L(G) and

ICI = a1L(G). Thus IM I+ ICI< 3p/4 and so p/2 5 ICI< 3p/4.
Now, the edges in matching M cover exactly ZIMI vertices,

so there exists p—ZIMI weak vertices in G, relative to M.

No two of these weak vertices can be adjacent, otherwise M

could be enlarged by including the edge joining these two

weak vertices, contradicting the fact that M is a matching.

Therefore there exists at least p-2IMI independent vertices

in G. Since IMI < %'p - ICI, then p - 2H4| > 2ICI - p/Z.

78

If p is even, there exists at least 1 + 2ICI - p/z independ-
ent vertices in G. Since ZIC I3 p then IC I+ 1 3 pl2, and
2ICI - p/Z + l >I CI. If p is odd, there exists at least
2ICI - [p/2]independent vertices in G. Since 2ICI 3 p and

p is odd, then 2ICI > p,I C I> [p/z], and 2ICI - Lp/z] >'ICI.
But C is an edge covering this implies that G has at most

IC Iindependent vertices. In any case a contradiction. This

completes the proof of the theorem.

The equality a1L(G) + BlL(G) = 3p/4 can be attained for
certain graphs G whose order is a multiple of four. A very
simple example is afforded by G = P4, a path of length 3.
Here A1(P4, M, C) assumes only two values, namely 3/4 and 1.
A more general example is given by taking for G the union of
n vertex disjoint copies of P4. By adjoining suitable edges
one can easily obtain a connected graph for which equality
holds.

We next consider properties of graphs which attain this
minimum possible value of the Gallai ratio, and employ an

argument similar to that used in theorem 5.6.

Ippppgm ,7. Let G be a graph of order p = 4n. Then a1L(G)
+ le(c) = 3p/4 if and only if a1L(G) . W2 and BlL(G) = p/,.
2399;: Suppose that a1L(G) + 81L(G) = 3pI4, so p is a

multiple of four, and p/2 S alL(G) < 39/4, Let M be a

79

matching with IMI = 81L(G) and C a covering withI CI = a1L(G).
Now the matching M covers exactly ZIMI vertices of G, so
there are p-ZIMI weak vertices with respect to M, no two of
which can be adjacent. Hence there are at least p-2IMI
independent vertices in G. We next show that there are at
least two such weak vertices. Since IMI = 3p/4 - ICI, then
p - ZIMI = 2ICI - p/z, and since p/2 5 ICI < 3p/4, we have
2ICI 3 p, and p - ZIMI 3 p/23 2. There are p - ICI compo-
nents in C , hence G has at mostI CI independent vertices
in-G. Then p/2 5 2ICI - P/Z 5 ICI. so I CI 5 p/Z.

Thus IC |= p/2 and IMI = pl4. The converse is trivial.

In the remainder of this section, we prove two theorems
which relate matchings and coverings to the Gallai ratio of
a graph. They provide a characterization of graphs for
which every covering (or every matching) contains the same

number of edges.

fIheorem 5,8. Let G be a graph of order p. Then u1L(G) =
u1U(G) if and only if A1(G,M,C) 5 l for all matchings M and
coverings C of G.

ggggg: If a1L(G) = a1U(G), then for any matching M
and covering C, we have
ICI + I MI5 610(6) + 810(6) = (111(6) + 810(G) = p, by Gallai's

theorem. Hence A1(G,M,C) 5 l.

80

Conversely,if A1(G,M,C) 5 1 for all matchings M and
coverings C of G, then by Gallai's formula

p = a1L(G) + 81U(G) s a1U(G) +81U(G) s p-
Thus a1L(G) = “10(6)-

Cozpllary: Let G be a graph of order p. Then a1L(G)=a1U(G)
if and only if A1(G,M,C) 5 l for a maximum matching M and a

maximum covering C of G.

Theprem 5,9. Let G be a graph of order p. Then 81L(G) =
81U(G) if and only if A1(G,M,C) 3 l for all matchings M and
coverings C of G.

2299:: If 81L(G) = 81U(G), then for any matching M of
G and any covering C of G we have

ICI +I MI 3 a1L(G) + BIL(G) = a1L(G) + 310(9) = p-
Hence A1(G,M,C) 3 1.

Conversely, if A1(G,M,C) 3’1 for all matchings M and
coverings C of G, by Gallai's formula

p = sum) + alum) 2 sum) + sum) 2 p.
Hence 81U(G) = 81L(G).

Cppollary: Let G be a graph of order p. Then 81L(G)=31U(G)
if and only if A1(G,M,C) 3 l for a minimum matching M and

a minimum covering C of G.

CHAPTER 6

VERTEX COVERINGS AND INDEPENDENT SETS OF VERTICES

Spcpion 6,1. Many of the concepts which we have developed
in our study of edge matchings and edge coverings can be
extended to maximal independent vertex sets and to vertex
coverings. As was the case for maximum edge matchings and
minimum edge coverings, earlier investigations have been
devoted almost exclusively to the study of maximum indepen-
dent sets of vertices and minimum vertex covers. Little or
no attention has been given to a general study of indepen-
dent vertex sets and to vertex covers. We find it possible
to define vertex coverings and maximal independent vertex
sets in a more general way. We again assume that the graphs

considered have no isolated vertices.

Qgfiipitipp_§51. A vepgpx povering set C0 is any subset of
the vertex set V(G) of G, which covers all the edges of G.

In particular, V(G) itself is a vertex covering set for G.

Dgfipition 6,2. A vpggex cpvering is a vertex covering set

which is minimal, in the sense that it contains no proper

81

82

subset which is also a vertex covering set.

Let aOU = a0U(G) denote the number of vertices in a
vertex covering having maximum cardinality and “OL = aOL(G)
the number of vertices in a vertex covering with minimum
cardinality. Let G be any (p.q) graph with no isolated
vertices, and C0 any vertex covering of G of order do. Then
the following inequalities are obvious:

l 5 “OL'S a0 5 “DU 5 p-l.

Furthermore, there exist graph G such that a0U(G) = p-l and
aOL(G) = 1, so both bounds are attainable. In fact, both
bounds can be attained with a single graph, as shown by the
example of a star graph S of order p. Clearly aOU(S) = p-l,
and a0L(S) = 1. It is readily seen that there exist only
two vertex coverings for S. This example also shows that
one cannot obtain an intermediate value theorem as was the
case for edge coverings, since for any integer K such that
l < K < p-l there is no vertex covering CO such that ICOI=K.
We next define a maximal independent set of vertices

for a graph G.

Definition 6,3. Ag independent vertex set no is any subset
of the vertex set V(G) of G with the property that no two

vertices in MO are adjacent.

83

Definipipn 6,4. A maximal independent vertex set is an
independent vertex set Mo which is maximal. This means that
M0 ceases to be an independent vertex set if any vertex of

G not in M0 is adjoined to M0.

Let BOU = BOU(G) denote the number of vertices in a
maximal independent vertex set having maximum cardinality,
and 80L = BOL(G) in one having minimum cardinality. Let G
be a (p,q) graph and MO any maximal independent vertex set
with order Bo. Then it is clear we have

1 .<.. BOLS BO 5. BOU 59’1-

We again consider the example of a star graph S of order

p 3 3, for which BOL(S) = l and BOU(S) = p-l. There are
clearly only two maximal independent vertex sets for 8, one
consisting of the center of the star graph S and the other
consisting of the remaining vertices. We again see that no
intermediate value theorem is possible. If K is any integer
such that BOL(G) < K < 800(6), there may or may not be a
maximal independent vertex set having order K.

Gallai [10] has shown that for any graph G, of order
p: “0L(G) + 80U(G) = D.

We will prove in this section a rather surprising
variation of Gallai's result, namely that

aOU(G) + BOL(G) = 9.

Thus Gallai's theorem also holds when the subscripts L and

84

U are interchanged. First we need to establish the fol-

lowing.

Lemma 6,l. Let G be a graph of order p having no isolated
vertices. Then Co is a vertex covering for G if and only if
the complementary vertex set M0 = V(G) - CO is a maximal
independent set in G.

2:99;: Let C0 be a vertex covering for G. Now
Mo = V(G) - Co is an independent set of vertices, for if
there exist two vertices v1 and v2 in M0 which are not
independent, then v1 is adjacent to v2 and the edge
e = (v1,v2) is not covered by any vertex in 00' This
contradicts the assumption that CO is a vertex covering.

We next prove that M0 is maximal. Suppose that M0 is
not maximal, so that there exists a set UWC Co such that
UIJ Mo is an independent set of vertices. Let u e U, so u
is joined only to vertices in C0 and not to vertices in MO.
Then CO-u is also a vertex covering, contradicting the
minimality of CO.

Conversely, let MO be a maximal independent vertex set
for G, and set Co = V(G) - M0. Then CO must be a vertex
covering set, for if there exists an edge not covered by C0
this edge must join two vertices in M0, contradicting the
assumption that the vertices of MD are independent. The set

C0 is also a vertex covering. If the contrary is assumed,

85

then C0 has a proper subset R which is a vertex covering
set. Let v 6 CO - R. Then v is joined only to vertices in
Co, for if v is joined to some vertex in M0 by an edge e,
this edge e clearly is not covered by R. But if v joins
only vertices in CO, then MOIJ Iv} is an independent set of
vertices. contradicting the maximality of M0. Thus C0 is

a vertex covering.

We can now prove our principal result of this section,
an extension of Gallai's well known result for minimum

vertex covers and maximum sets of independent vertices.

Thgggem 6,1. Let G be any graph of order p with no isolated
vertices. Then a0U(G) + BOL(G) = p.

2399;: Let CO be a vertex covering of maximum order
aOU(G), and let M0 = V(G) - Co. By lemma 6.1. MO is a
maximal independent vertex set, we seek to show that
IMOI = BOL(G), that is that MO has the minimum number of
vertices possible. If M0 is not a minimum, then there
exists a maximal independent vertex set M0* such that
|M0*I < I MOI. Let 60* = V(G) - M *. By lemma 6.1. 60* is
a vertex covering andI CO*I > ICOI. contradicting the
assumption that CO had maximum order. Hence M0 is a
minimum maximal independent vertex set, andI MOI = BOL(G).

Since ICOI +I MOI = p, the theorem follows.

86

It is obvious that the assumption made in theorem 6.1.
that G has no isolated vertices is not essential. Suppose
there exists a set N of isolated vertices in G. Then we
can set G = G - N, andI G I= p - n, whereI N I= n. By
theorem 6.1. a0U(G) + BOL(G) = p-n. Since aOU(G) = aOU(G)
and BOL(G) = BOL(G) - n, then aOU(G) + BOL(G) = p.

Secpion 6,2. We again consider graphsG of order p having
no isolated vertices. We have observed in section 6.1. that
for any maximal independent vertex set MO of G:

l _<_ BOL(G) sI MOI s 800(6) _<_ p-l.
and for any vertex covering C0 of G, we have:

1 s “01“” SI COI _<_ «00(6) 5 p-l.
From these inequalities we readily obtain:

P - P p

Dpfipipipn 6,5. For an arbitrary maximal independent set

of vertex M0 and an arbitrary vertex covering C0 of a graph

G, we define the vergex Gallai patip
o'.

_ IMOI +IC

We first show that there exist graphs G and suitable
maximal independent vertex sets and vertex coverings of G

such that the Gallai ratio is arbitrary close to the lower

87

bound 0 and to the upper bound 2. To Show this, let G be

a star graph of order p, then aOL(G) = BOL(G) = l and

+ 8
A0 = EQL_E__QL = % . Clearly A0 is arbitrary near 0 when

p is sufficiently large. Also aOU(G) = BOU(G) = p-l and

a + B
0” p 0U = 2 - % . It is evident that A0 will be

A0 =
arbitrary near 2, when p is sufficiently large.

Next we prove a theorem which relates independent
vertex sets and vertex coverings to the vertex Gallai ratio
of a graph. It also providesa characterization of graphs
for which all vertex coverings contain the same number of

vertices and all maximal independent vertex sets also have

the same number of vertices.

Ihgopgp 6,2. Let G be a graph of order p. Then the fol-
lowing three statements are equivalent.

(1) aOL(G) = a0U(G).

(2) BOL(G) = BOU(G).

(3) AO(G,M0,CO) = l for all maximal independent
vertex sets MO and vertex coverings C0 of G.

2299;: (1) implies (Z). By Gallai's theorem
p = a0L(G) + BOU(G) = aOU(G) + BOU(G), and from theorem 6.1.
p = a0U(G) + BOL(G). Hence BOL(G) = BOU(G).

(2) implies (3). For any maximal independent vertex

set MO and vertex covering CO, we have:

88

ICO I+ I MoI S aOU(G) + BOU(G) = aOU(G) + BOL(G) = p: by
theorem 6.1. Hence AO(G, M0, C0) 5 1. Furthermore,
IcoI + I MOI = I CC I + BOU(G) 3 aOL(G) + scum) = p. by
Gallai's formula. Hence A0(G, MO, CO) 3 l, and we conclude
that AO(G, M0, CO) = 1.

(3) implies (1). Since p = aOL(G) + BOU(G) = a0U(G) +

BOU(G) then a0L(G) = a0U(G).

It is interesting to compare theorem 6.2. with the
analogous results obtained for edge matchings and coverings
in theorem 5.8. and theorem 5.9.

Remapk: If for some graph G, a0L(G) # QOU(G), (or if
BOL(G) # BoU(G)), then the vertex Gallai ratio AO(G) assumes
values less than unity and also greater then unity. By
theorem 6.2. a0L(G) f aOU(G) implies BOL(G) # 300(6), and
vice-versa. From theorem 6.1. aOU(G) + BOL(G) = p and this
implies that “00(6) + BOU(G) > p and also that a0L(G) + BOL(G)
< p. The last two inequalities show that AD > 1 and Ao< 1

both occur for such graphs.

CHAPTER 7
DOMINATING NUMBERS

Sgction 7,1. Dominating numbers have been discussed by
Ore [22] and also by Berge [1], who refers to them as
coefficients of external stability. An application of
dominating numbers which readily comes to mind is the
problem of the five queens. In the game of chess, what is
the fewest number of queens which can be placed on a stand-
ard chessboard so that every square is guarded (dominated)
by at least one of the queens? It is easy to show that
five queens can be placed so that this condition is satis-
fied, and that no fewer suffice.

In this chapter it is assumed that G is a (p,q) graph

which has no isolated vertices.

D i ' n 7 . A subset D0 of V(G) is called a vpppex
gomippping set, if every vertex of G not in D0 is adjacent

to at least one vertex in D0'

Dpfiinipipn 7,2. A vertex dominating set D0 is called

minimal if no proper subset of D0 is a vertex dominating set.

89

90

Let us denote the minimum and maximum number of
vertices in any minimal vertex dominating set of graph G
by 60L = 60L(G) and dOU = 60U(G) respectively, and refer
to these parameters as the vertex dominating numbers. If
D0 is any minimal vertex dominating set of order do, then
it is clear that l 5 60L 5 do 5 dOU 5_p-1.

A star graph S of order p serves as an example to show that
the upper and lower bounds for do can both be attained.
since 60L(S) = l and GOU(S) = p-l. From this example it is
also evident that there exist only two minimal vertex
dominating sets for S, and hence in general there is no
possible intermediate value theorem as in the case of edge
coverings and edge matchings. The range of values of 60(6)
may therefore be expected to contain gaps.

Ore [22] proved that an independent vertex set is
maximal if and only if it is a vertex dominating set. We

shall prove the following generalization:

ngpppm 7,1. An independent vertex set is maximal if and
only if it is a minimal vertex dominating set.

2399;: Let Co be a maximal independent vertex set. If
C0 failed to be a vertex dominating set, then there exists
some vertex v in V(G) - C0, such that v is not adjacent to
any of the vertices in Co. Then Col) {v} forms a larger

independent set of vertices, which contradicts the maximality

91

of CO. Hence C0 is a vertex dominating set. If C0 is not
minimal ( as a dominating set). then there exists a vertex
u in CO such that CO - Iu} also forms a vertex dominating
set. But vertex u fails to be dominated by CO - {u}, a
contradiction.

Conversely, let D0 be any independent vertex set which
is also a minimal vertex dominating set. If DO were not a
maximal independent vertex set, then there exists some
vertex w in V(G) - D0 such that {wIIJ D0 is an independent
vertex set. This implies that w is not dominated by D0,

again a contradiction.

The vertex independence numbers are bounded above and

below by the vertex dominating numbers.

Cpppllary 7,1. For any graph G of order p.

1 _<. GOL(G) s BOL(G) s scum) .<_ aoum) _<_ p-l.

Prppf: Since from theorem 7.1. every maximal independ-
ent set of vertices is a minimal vertex dominating set. the

result follows immediately.

There exist graphssuch that BOU < GOU and there are
graphs such that dOL< BOL' For example, consider the

following graphs shown in the figure 7.1. and figure 7.2-

92

 

A 7 6

Figure 7.1. A graph illus- Figure 7.2. A graph illus-
trating BOU(G1) < GOU(Gl)' trating GOL(GZ) < BOL(G2).

Then BOU(Gl) = 2 and 60U(G1) = 3, since the vertices A, B,
and C form a minimal vertex dominating set. Where OOL(G)==3
and BOL(G2) = 5. Here the vertex set IA,B,C} and I1,2,B,6,7}
can be used.

Definitions can be made for minimal edge dominating
sets analogous to those made for minimal vertex dominating

sets.
Definition 7,3. A subset D1 of E(G) is called an edge

dppinating set if every edge of G not in D1 is adjacent to

at least one edge in D1.

nginipipn 7,4. An edge dominating set D1 is called

minimal if no proper subset of D1 is an edge dominating set.

We denote by 61L = dlL(G) and dlU = 61U(G) respectively

93

the minimum and maximum number of edges in any minimal edge
dominating set of G and refer to these parameters as the
edge dominating numbers. If D1 is any minimal edge domi-
nating set having cardinality 61, then

150' 5d

5 d S 9-2.

1L 1 1U
The fact that p-2 is an upper bound for 61 will be shown
later. A star graph S of order p is an example showing
that the lower bound can be attained, and the following

figure 7.3. shows that the upper bound p-Z is also attain-

able. v1

 

Figure 7.3. 61U(G) = p-Z.

Then dlu(G) = p-2, as can be seen by considering the edge
set {(vi,vp)I i = l, 2, . . .. p-Z}. Also olL(G) = 2, and
there are no minimal edge dominating sets whose cardinality
lies between 2 and p-Z. Thus no intermediate value theorem
is possible, and the range of values of the edge dominating
numbers may contain gaps.

We next Show that p-Z is indeed an upper bound for dlU'

94

Suppose a graph G of order p has a minimal edge dominating
set D1 such that ID1I = p-l. Each component of the edge
induced graph <D1> is a star graph, so <D1> is a forest.
Supposing that <D1> has p' vertices, then <Dl> has p'- A
edges, where A is the number of components in <D >. Then
by hypothesis p' - A = p - l where A33 1, so p'.3 p. Hence
p = p' and A = l, i.e. <D1> is connected and is a spanning
star graph. If we consider any edge of G not in D1 dom-
inated by an edge (v1,v2) of D1, it is clear that it is
already dominated by other edges of D1. Then D1 - (v1,v2)
also forms an edge dominating set, contradicting the
minimality of D1. ThereforeI D1I 5 p-Z.

There is a relation between edge matchings and minimal

edge dominating sets, as shown in the following

Theorem 7,2. An independent set of edges of a graph G is
a matching for G if and only if it is a minimal edge
dominating set.

2599;: Let M be an edge matching. If M fails to be an
edge dominating set, then there exists an edge e in E(G) - M,
which is not adjacent to any edge of M. This implies that
Mi){e} is an independent set of edges contradicts the
assumption that M is a matching. Hence M is an edge dom-
inating set. If M is not minimal, then there exists an

edge e' in M such that M - {e'} also forms an edge dominating

95

set, but then edge e' is not dominated by M - Ie'}, a
contradiction. Thus M is a minimal edge dominating set.
Conversely, let D1 be an independent set of edges
which is a minimal edge dominating set. If D1 were not a
matching, then there exists an edge e“ in E(G) - D1 such
that DliJIe”I is an independent set of edges. However,
this implies that edge e" is not dominated by D1, a con-

tradiction.

The following corollary is the analog of corollary 7.1.
shows that the edge independence numbers are bounded above

and below by the edge dominating numbers.

C l a 7 . For any graph G of order p we have
Pgoofi: Since from theorem 7.2. every edge matching is

a minimal edge dominating set, the result follows immediately.

There exist graph having BlU < d1U‘ For example from
the adjoining figure 7.4.

G A
9

Figure 7.4. A graph illustrating BlU(G) < 61U(G).

96

We have BlU= 2 and dlU = 5.
The situation is quite different for the parameters
BlL(G) and dlL(G). We have the following.

Theorem 7,3. For any graph G with no isolated vertices,

a1L(G) = s,,(e).

In order to establish this equality, we need the

following.

Lemma 7,1. Let D1 be a minimal edge dominating set of G,
having minimum cardinality, sol 01' = dlL(G). Suppose that
the edge induced subgraph <D1> has a component C which is a
star graph different from K2, soI C I3 3. Then there exists
a non-empty set of at leastI C I- 2 vertices in G - <D >.
which are joined to at leastI C I- 2 end vertices of the
component C.

2599;: Define W = G - <D1>. The graph W is a set of
independent vertices, for if two vertices of W were joined
by an edge e, then e is not dominated by D1, a contradiction.
LetI C I= n+1, where n 3,2. Since D1 is an edge dominating
set in G of minimum cardinality, each edge of C dominates
at least one edge of G not in C, since otherwise such an
edge of C could be omitted from D1, a contradiction.

We maintain it is always possible to choose a set of

97

distinct vertices ul, “2’ . . .. um in W, such that (1) no

three end vertices of C can be joined to a single vertex

of W and to no other vertices of W and (2) no two (or more)

pairs of end vertices of C can be joined to two (or more)

distinct vertices of W and to no other vertices of W.
Suppose there exists three end vertices v1, v2, v3 of

C which are joined to a single vertex u1 of W and to no

other vertices of W, (see figure 7.5.)

Figure 7.5. Three end vertices of C, joined to a
single vertex of W.

Then we can delete edges a and b from D1 and add edge e to
D1, thereby obtaining a new edge dominating set with smaller
cardinality thanI 01" a contradiction.

Next suppose that there exists two pairs of end vertices
of C which are joined to two distinct vertices u1 and u2 of

W and to no other vertices of W, (see figure 7.6.)

Figure 7.6. Two pairs of end
vertices of C, joined to two
distinct vertices of W.

 

98

Then we can delete edges a, b, c from D1 and add edges d, e
to D1. We obtain a new edge dominating set with cardinality
less than IDII, a contradiction.

From (1) and (2) we conclude that at most two end
vertices of C can be joined to a single vertex of W, there-
fore m 3,n-1. Hence there exists a non-empty set of at
least IC I- 2 = n-l vertices in W, which are joined to at

least n-l end vertices of the component C.

We are now able to complete the proof of theorem 7.3.
Let D1 be a minimal edge dominating set havingI DlI = 61L(G).
It is clear from corollary 7.2. that dlL(G) 5 81L(G). If
D1 is also an independent set of edges, then D1 is an edge

matching and 61L(G) 3,81L(G), so 61L(G) (G), and the

= 51L
theorem is proved in this case.

If D1 is not an independent set of edges, then at
least one of the components of <Dl> is a star graph dif-
ferent from K2. Let A where Ci denotes the i-th

<D > = U C.,
1 i=1 1

component of <D1>, i = l, 2, . . ., A. Consider a component
C1 of order n1+l, where n1 3 2. By lemma 7.1. there exists
at least nl-l vertices in G - <D1> which are joined to

nl-l end vertices, say v12, v13, . . ., Vin; of the graph
C1. Now we are going to construct a new edge dominating

set by replacing the edges (v10, v12), (v10, v13), . . .

 

99

. .. (v10, Vlnl) by the set of edges (v12, ulZ)’ (v13, u13),
. . ., (vlnl' uln1)' Let us denote this edge dominating
set by D11. It is clearI Dll = IDllI. Suppose that a

component C2 in <D1> has order n2+1, where n23 2. We claim

there is no end vertices of C2 can be joined to vertices

uli's only, and to no other vertices of W. For example

figure 7.7.
C1 C2
v10 v20
V1n
1 V21 v2n
vll vli‘ v 2
23
3‘,
uli=u2j

Figure 7.7. An end vertex of C2 joined to vertex uli'
If, v23 13 jOIned to uzj = “11’ then D11 — (v20, v2j) is
an edge dominating set, which contradicts the minimality of

D From this assumption and lemma 7.1. there exists at

1.
least nz-l vertices in G - <D1> namely “22' u23, . ., uznz
different from "11’ “12’ . . ., u1n1 which are joined to
nZ-l end vertices of C2, say v22, v23, . . ., VZnZ' Now,

we may construct a new edge dominating set D12 by replacing

the set of edges (v20, v22), (v20, v23), . . .. (v20, V2n2)'
by the set of edges (v22, uzz), (v23, u23), . .. (V2n2'u2n2)'

100

After a finite number of such steps, all components in the
edge dominating set are reduced to single edges, and no
star component different from K2 exists. The remaining
edges in these components must then be independent, and
therefore form an edge matching. Thus dlL(G) 3 BlL(G)' and

equality follows.
An application of theorem 7.3. is the following.

Ipeppgm 7,4. Let G be a graph of order p, and having no
isolated vertices. Then 60L(G) + olL(G) 5 p.

2292;: Let D0 be a minimal vertex dominating set such
thatI DOI = OOL(G). Define w = V(G) - DO. If IDOI 5,9/2.
then dOL(G) + dlL(G) = IDOI + 81L(G) 5,p, since no independ-
ent edge set has more than p/2 elements.

Suppose next thatI DOI > plz. We first note that if
v1 is in D0 and is incident with a vertex v2 in D0, then
there exist at least one vertex u1 in W such that u1 is
dominated only by v1 and not by any other vertices in Do.
For if the set of vertices in W which are dominated by v1
are also dominated by some other vertices in D0’ then since
v1 itself is dominated by v2, this implies that DO - {v1}
will be a vertex dominating set. This contradicts the
minimality of Do.

Now, let M1 be a minimum edge matching in G, so

101

|M1I 8 BIL(G) = dlL(G). M1 is a set of independent edges,
which join pairs of vertices in DO’ or in W, or join a
vertex in Do to one in W. Suppose there exist r edges in
M1 which join two vertices in D0’ then there are at least
2r vertices in W which cannot join vertices in D0 to form
edges in M1, by the previous argument. Now, we may form an
upper bound for IMII by joining these 2r vertices in W by

r edges and join the remaining IWI - 2r vertices of W to

 

rm '
.

vertices in D0’ This is possible sincel DOI >I WI. Thus
|M1I5,r + r +4 W I- 2r =I‘WI. This shows thatI MII is
bounded above by IWI, and is independent of the number of
edges chosen from the set <D0>. Hence we conclude that

60L(G) + cum) =ID0I +IM1I _<_IDOI +IWI= p.

We have considered in this chapter sets of edges which
dominate all edges of a graph G, and also sets of vertices
which dominate all vertices of C. One might wonder if it
would be useful to consider sets of edges which dominate
all vertices of a graph, or sets of vertices which dominate
all edges.

A moment's reflection convinces one that under the
usual interpretation of domination, the parameters arising
are exactly the edge and vertex covering numbers discussed

in chapters 4 and 5.

102

Segpion 7,2. This final section contains a few miscella-
neous results on line graphs. The line graph LG of G by
definition has a vertex set V(LG) which is in one-to-one
correspondence with the edge set E(G) of G. Two vertices
of LG are adjacent if and only if the corresponding edges
of G are adjacent. The line graph of G is sometimes called
an interchange graph or derivative of G. Gupta [ll]
mentioned without proof a few results concerning the
relationship between minimum covers and maximum matchings
for line graphs. We present a few new ones. We assume G is
a (p,q) graph and has no isolated vertices. It is clear
that 800(LG) = 31U(G). BOL(LG) = 81L(G)-
and dOU(LG) = 61U(G), GOL(LG) = 61L(G).
From Gallai's formula we readily have

aOL(LG) + BOU(LG) = q.
Hence aOL(LG) = q - BOU(LG) = q - 81U(G).
From theorem 6.1. we have

GOU(LG) + BOL(LG) = Q.
Hence a0U(LG) = q - BOL(LG) = q - 81L(G)

We also have the following.

Ihggzem 7,5. Let G be a graph with no isolated vertices.
Then BOL(LG) = 60L(LG)
Pgopf: Now BOL(LG) = BlL(G) and GOL(LG) = 61L(G).

103

By theorem 7.3, 81L(G) = 61L(G). Hence we conclude that

szpllazy 7,3. Let G be a (p,q) graph which has no
isolated vertices. Then OOL(LG) + aOULG) = q.

The proof is trivial and is omitted.

 

 

 

 

104

N m N N N Ts a
and TL E s We “as“ a-.. Ev ms Ame a-.. so. a

u 3 Home:

a . E . E a a E a a E a c c v a
. Ac.EvM
a a a a m a a a a a a Ao.ove rash»
soapstone
H-m a a H H-o a H-a a A a H-o H-a Aa-m.ave
sebum noun

 

are

GN co oHomo

cw»

mu m E

cm)
W

E?

.1?

 

M m as 3 we K.

35;?

 

HI
to)
I:
W
"'T‘
N
‘E.

V
w 5mm; am room
M

 

 

a

a a I I a H H-a H-o I I I H-a
ma mag mag mag a ouoaaaoo
not use ass mom son mos see use see use nae romeo

 

 

 

 

 

 

 

 

 

 

 

 

 

mnemuu mo momemfio Gamuuoo How mumuoamumm mo oHnMH

 

105

 

OH

Nana
monoe£MmOmHe

 

OH

ma

«H

OH

CH

«a

CNN—Q
COHmvaNUmUOD

 

can“
GOHUQSMUUO

 

mug
”DDU

 

can
couommmwuoh

 

calm macaw
cmmuouom one

 

03V

Omfl

GIN

Okfl

QMV

cum

GIN l‘

Gun

emu

neoo

 

min([§]. p-pj)

p‘pj

p'pl

.. 'P
p min(L-2-]. 13-13,) cm m

p-pl

H"
flaw..qWNmWHQ
.HAfiQ o o o .NQ

QVM madam
sunfish
1n ouoHQEOQ

 

 

do

 

sop

 

 

 

40m

 

 

mos

 

 

 

:3 P
r4 min<£§19 P'PJ)

 

A

F‘
d

as

macho

 

 

 

 

10.

11.

12.

13.

106

BIBLIOGRAPHY

C. Berge. The Theory pf Graphs. Methuen, London (1962).
C. Berge. Two The rems in Gra h Theor . Proc. Nat.
Acad. Sci. USA. 53(1957), 842-844.

C. Berge. Gra hs and H er ra hs. North-Holland,

London (19735.

M. Behzad and G. Chartrand. An Introduction to the
Theory of Graphs. Allyn and Bacon, Boston (1972).

L. M. Beineke and M. D. Plummer. On the l-Factors of
a Non-sepprable Graph. J. Combinatorial Theory 2 (1967),
285-2 90

G. Chartrand, D. Geller and S. Hedetniemi. Gpaphp gigh

Forbidden Subggaphs. J. Combinat. Theory 10B 1971 ,
12" 10

J. Edmonds. C ve s and Packin s in a Famil f Se 3.
Bull. Am. Math. Soc. §§_(1962I, 494-499.

J. Edmonds. Paths T ees and F1 wers. Canad. J. Math.
21 (1965), 449-467.

R. Forcade. Smallest Maximal Matchings in php Gpaph of
e d-dim nsi nal Cube. J. of Combinatorial Theory.

Series B. lfl_no. 2 (1973), 157-162.

T. Gallai. Uber extreme Punkt-und Kantenmen en. Ann.

gggv. Sci. Budapest, Eotvos Sect. Math. 2 1959), 133-

R. Gupta. Indeppndence and Covering Numbers pf Ling
Graphs and Tptal Graphs. Proof Techni ues in Gra h
Iheopy. Academic Press, New York (l§6§), 61-62.

B. Granbaum. 8 me Problems Conce in Gra hs. Univ.
of Washington (1972).

B. Grunbaum. Networks. (To appear.)

14.
15.

16.
17.
18.

19.
20.
21.
22.

23.

24.
25.

26.

107

F. Harary. Graph Thepry. Addison-Wesley, Reading
(1969).

S. Hedetniemi. On Herpgitary Properties of Graph .
Studia Sci. Math. Hungar. l9 2 .

E. A. Nordhaus, B. M. Stewart and A. T. White. On the
Maximum Genus of a Graph. J. Combinatorial Theory.

E. A. Nordhaus. Ongphe Density and Chromatic Numbers

pf Graphs. The Man Facets of Gra h Theor . Springer-
Verlag, Berlin (1969).

R. Norman and M. Rabin. An Al orithm for a Minimum
vaer of a Gpaph. Proc. Amer. Math. Soc. 29 (1959),
315-3190

0. Ore. Arc Coverings of Graphs. Ann. Mat. Pura. Appl.
O. Ore. Incidence Matchin s in Gra hs. J. Math. Pura.
Appl. QQ_(9I (1961), 123-127.

0. Ore. Graphs and Matchings Theorems. Duke Math J.
22 (1955), 625-639.

0. Ore. Theor of Gra hs. Amer. Math. Soc. Colloq.
Publ. 38, Providence (1962).

D. Ray and Chaudhudi. An Algorithm for a Minimum

Cgv%p pf an Abstract Cpmplex Chains. Canad. J. Math.
.1- 196 g 11" 4o

M. J. Stewart. G a he and Their Subdivisions. Ph.D.
Thesis, Michigan State University (1972).

J. H. Weinstein. On the Number of Dis'oint Edges in a
Gpaph. Canad. J. Math. 55 (1963), 106-111.

C. WitZgall and C. Zahn. Modification pf Edmonds'

MaxImum Matching Algorithm. J. of Res. N. B. S. 92
Bo 196 p 91-980

 

 

   

MICHIGAN STATE UNIVERSITY LIBRARIES
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
3 1293 03146 3445 ‘