International Journal of Scientific & Engineering Research Volume 2, Issue 10, Oct-2011 1

ISSN 2229-5518

The m-deficient number of complete bigraphs

Sanjay Roy, Dr. Danappa G.Akka

Abstract— An open problem p os ed by Aaron and Lewinter in [2] as ks whether the m -def ic ient number interpolates or not. A negative ans wer of this problem is established in [5]. The c ounter example in [5] was obtained by c haracterizing the m -defic ient number of c omplete graph. In

this note an other c ounter example was obtained by c haracterizing the m-defic ient number of c omplete bipartite way.

Index Terms— Key words: Interpolate, deficient number, Degree preserving

Subject classification: 05C99 (Graph Theory).

Kn n

2, n1 ≠ n2 in a s imilar

INTRODUCTION

——————————  ——————————
An integer valued function of on the spanning tree set of a graph G is called interpolating if when ever an Integer k satis- fies f(T)<k<f(T1) for spanning trees T and T1, there exists a spanning tree T11 such that f (T11)=k. Thus interpolation may be thought of as a discrete analogue of the intermediate value property. A vertex v of Spanning tree T of a graph G is called degree preserving (DP) if degVT =degV . It is shown in [4] that the number of degree preserving vertices interpolate over the spanning tree set of a graph. In [2], the concept of degree pre-
n1+n2
∑ di =2 (n1+n2 – 1)
i = 1
The above Lemma 1 is useful to establish the following
Theorem 1.

Theorem1.

Let m, n1, n2 be three integers such that
o ≤ m ≤ n1+n2 -2. Then an integer k ≥ 0 is an m-deficient
serving is generalized as follows: A vertex v of spanning tree T
number of Kn

n2 if and only if

of a graph G is called m-deficient if degV
- degVT
=m. Note
that a degree preserving vertex v is O-deficient. An integer k is an m-deficient number of graph G if there is a spanning tree T of G such that k=N (G, T, m). That is N (G, T, m) denote the k number of m-deficient vertices in T.
The set of deficiencies of spanning trees of a graph G may differ, it is shown in [2] that the sum of the deficiencies of the vertices of any spanning tree of G is invariant. If G has ‘n’ vertices and ‘e’ edges, the sum of the deficiencies in any spanning tree is 2(e-n+1). If G is a planar graph with f faces then by using Euler’s planar graph formula the sum of defi- ciencies is 2(f-1).
An open problem posed by Aaron and Lewinter in [2] asks whether the m-deficient number interpolates or not. A nega- tive answer of this problem is established in [5]. The counter example in [5] was obtained by characterizing the m-deficient number of complete graphs. In this note another counter ex- ample was obtained characterizing the m-deficient number of complete bipartite graphs.

RESULTS

The following Lemma is equivalent to 2.1.10 [3].

Lemma 1. Let d1, d2,….,, dn1, dn1+1, ….., dn + n2 be the de- gree sequence of a graph of order n1+n2. Then there is a span- ning tree T of the complete bipartite graph

Kn1,n2 (n1 ≠ n2) with vertex set V={v1,v2,…., vn1+ 1,…., vn1+

n1} such that deg vi = di for 1≤ i ≤ n1+n2 if and only if

n1+n2-2
k ≤ ----------- k ≠ n1+n2-3 ni - m-1

Proof.

Obverse that Kn1, n2 is a complete bigraph with degrees n1 and n2. If k is an m-deficient number of Kn1, n2 there is a spanning tree T of Kn1, n2 such that there exist exactly k ver-

tices in T with degree ni – m ≥ 2, i=1 or 2..
Hence we have k (ni - m) + (n1+ n2 - k) ≤ 2(n1+n2) - 2. This means k (ni - m) – k ≤ (n1 + n2) -2
That is (1)
n1+n2-2
k ≤ ------------
ni - m-1
If k= n1 + n2 – 3 then by (1) and the inequality ni – 2 ≥ m, we deduce m=ni -2 or ni-m=2. By Lemma 1, there are posi tive integers di ≠ 2 satisfying 1≤ i ≤ n1 +n2-k=3such that
3
2(n1+n2-3) + ∑di = 2(n1+n2-1)
i=1

Hence ∑di =4 which is impossible since di ≠ 2
i=1
for 1 ≤ i ≤ 3

International Journal of Scientific & Engineering Research Volume 2, Issue 10, October-2011 2

ISSN 2229-5518

Then consider following two cases

Case 1.

m = ni – 2
In this case, k ≤ n1+ n2 - 2 and k ≠ n1 + n2 - 3.The m-deficient vertices in a spanning tree T are precisely the vertices of de- gree 2 .When k=n1+n2-2, a Hamiltonian path of Kn1, n2 has k, m-deficient vertices. When K ≤ n1+n2 - 4,
we get d1=d2=…...=dk=2, dk+1= n1+n2-k-1 and dk+2 = dk+3=…..= dn1+ n2=1
Obviously

Corollary 3.

If m = ni -2 then k is an m-deficient number of

1, 2 if and only if

o ≤ k ≤ n1+n2-2

Corollary 4.

For every positive integer m, the m-deficient number of Km1+ 2, m + 2 does not interpolate.

n1+n2
∑ di = 2 (n1+n2-1)
i=1

and, in light of Lemma 1, there is a spanning tree T of Kn1, n2

such that

k=N (Kn1, n2, T ; m). Thus k is an m-deficient number of Kn1, n2

Case 2.

m ≤ ni -3
In this case, k ≤ (n1+n2-2) ∕ (ni - m-1) < n1+n2-3
Let j = k (ni – m -2) +2 Then j ≤ n1+n2-k let
d1=…….=dk=(ni-m)≥2, dk+1=…….= dk+j =1and dk+j+1=……..=

References

[1] D.G Akka and Nanda S. Warad, The m-deficient number of graphs, Graph Theory Notes of New York, LVI (2009)15-16,
[2] M. Aaron and M. Lewinter, o-deficient vertices of spanning trees, Graph Theory Notes of New York, xxvii : 5, New York Academy of Sciences (1994) 31-32
[3] J.A Bondy and U.S.R. Murthy, Graph Theory with Applica- tions, Macmillan, London (1976).
[4] M. Lewinter, Interpolation theorem for the number of de- gree- preserving vertices of spanning tree, IEEE Tran. Circuits

dn1+

n2=2.

system, Cas-34 (1987)205.
Then,
n1+n2
∑ di =k (ni-m)+j+2(n1+n2-k-j)
i=1
[5] J.Yuan, A note on a problem of Aaron and Lewinter about the m-deficient number of graphs, Graph Theory Notes of New York, xxviii : 9, New York
=k (ni-m-2) - j+2(n1+n2)
=2(n1+n2-1)
By Lemma 1, k is an m-deficient number of Kn n2
In the following corollary we given an another counter exam-
ple is established in similar way in [1]

Corollary1.

[1] Let m and n be two integers such that
o ≤ m ≤ n - 2. Then an integer k ≥o is an m-deficient number of
K n ,n if and only if
2n - 2
k ≤ ------------- and k ≠ 2n - 3
n – m -1

Corollary 2.

If o ≤ m ≤ ni - 3 then k is an m-deficient number of Kn1, n2 if

and only if
n1+n2-2 k ≤ ----------- ni - m-1