NUMBER ON

Internat. J. Math. & Math. Sci.

VOL. 13 NO. (1990) 205-206

2O5

A NOTE ON THE k-DOMINATION NUMBER OF A GRAPH

Y. CARO

Department of Mathematics University of Haifa-Oranim

Geva 18915 Israel

and Y. RODITTY Department of Mathematics

Beit-Berl College and School of Mathematical Sciences Tel-Aviv Universlty

Israel

(Received December 30, 1988 and in revised form February I, 1989)

ABSTRACT. The k-domlnation number of a graph G G(V,E),

Yk(G),

cardlnallty of a set X V such that any vertex in V X is adjacent to at least k vertices of X.

Extending a result of Cockayne, Gamble and Shepherd 4], we prove that

Yk

if (G)

n+-In

KEY WORDS AND PHRASES. k-dominating set and k-domination Number.

1980 AMS SUBJECT CLASSIFICATION CODE. 05C35.

INTRODUCTION.

A set X of vertices of a graph G G(V,E) ^is k-dominating if each vertex of V\X

is adjacent to at least k vertices of X. The k-dominatlon number of a graph G,

Yk(G),

We write (G)for the minimum degree of vertices in G and

IGI

number of vertices of G.

Several results concerning

Yk(G)

Yk A--’

As for the upper bound, Cockayne, Gamble and Shepherd proved the following:

THEOREM I.I. If G has p vertices and 5 k, then

Yk(G)

2. MAIN RESULTS.

Our aim in this note Is to extend Theorem 1.1 and give a shorter proof of that given in Cockayne, Gamble, and Shepherd [4]. We prove,

206 Y. CARO AND ^{Y. RODITTY}

THEOREM 2.1. Let n, k be positive integers and G a graph such that

(G) k-l. Then y,(G)

n m n+l

PROOF Let

VI,V2,...,Vn+

the number of edges in E’ where E’

E(G)\

i

>

i

By a classical argument of Erd6 [5] we have that for every x

n+l

degG(x)]

that

n

(n+l

degH(x) [

---]

n+l

Assume W.L.O.G. that

IVll IV21 ... _IVn+ll.

i=2

dominating set of G since each vertex x e V is adjacent to at least k vertices of A. Thus it follows that

Yk(G) p-IVl[

COROLLARY [4] If 6(G) > ^{k then}

Yk(G)

COROLLARY 2: If (G) 2k then

Yk(G)

REMARK. Using a similar argument we can prove the following:

If (G) k and X(G) n then y, (G) <

m n

REFERENCES

I. FINK, J.F. and JACOBSON, M.S., n-Domlnatlon in Graphs, Graph Theory with

Applications to Algorithms and Computer Science, Proc. of 5th international Conference, Kalamazoo (1984), 283-300.

2. FINK, J.F. and JACOBSON, M.S., On n-Domlnation, n-Dependence and Forbidden Subgroups, id. 301-311.

3. FAVARON, 0., k-Domination and k-Independence in Graphs, Technical report Orsay, France (1987).

4. COCKAYNE, E.J., GAMBLE, B., SHEPHERD, B., An Upper Bound for the k-Domination Number of a Graph. _J._of Graph_Theory ⁹ (1985), 533-534.

5. ERDOS, P., On some Extremal Problems in Graph Theory, Israel J. of Mathamatics

3(1965), 113-116.

Mathematical Problems in Engineering

Special Issue on

Time-Dependent Billiards

Call for Papers

This subject has been extensively studied in the past years for one-, two-, and three-dimensional space. Additionally, such dynamical systems can exhibit a very important and still unexplained phenomenon, called as the Fermi acceleration phenomenon. Basically, the phenomenon of Fermi accelera- tion (FA) is a process in which a classical particle can acquire unbounded energy from collisions with a heavy moving wall.

This phenomenon was originally proposed by Enrico Fermi in 1949 as a possible explanation of the origin of the large energies of the cosmic particles. His original model was then modified and considered under different approaches and using many versions. Moreover, applications of FA have been of a large broad interest in many different fields of science including plasma physics, astrophysics, atomic physics, optics, and time-dependent billiard problems and they are useful for controlling chaos in Engineering and dynamical systems exhibiting chaos (both conservative and dissipative chaos).

We intend to publish in this special issue papers reporting research on time-dependent billiards. The topic includes both conservative and dissipative dynamics. Papers dis- cussing dynamical properties, statistical and mathematical results, stability investigation of the phase space structure, the phenomenon of Fermi acceleration, conditions for having suppression of Fermi acceleration, and computational and numerical methods for exploring these structures and applications are welcome.

To be acceptable for publication in the special issue of Mathematical Problems in Engineering, papers must make significant, original, and correct contributions to one or more of the topics above mentioned. Mathematical papers regarding the topics above are also welcome.

Authors should follow the Mathematical Problems in Engineering manuscript format described at http://www .hindawi.com/journals/mpe/. Prospective authors should submit an electronic copy of their complete manuscript through the journal Manuscript Tracking System athttp://

mts.hindawi.com/according to the following timetable:

Manuscript Due March 1, 2009 First Round of Reviews June 1, 2009 Publication Date September 1, 2009

Guest Editors

Edson Denis Leonel,Department of Statistics, Applied Mathematics and Computing, Institute of Geosciences and Exact Sciences, State University of São Paulo at Rio Claro, Avenida 24A, 1515 Bela Vista, 13506-700 Rio Claro, SP, Brazil; [email protected]

Alexander Loskutov,Physics Faculty, Moscow State University, Vorob’evy Gory, Moscow 119992, Russia;

[email protected]

Hindawi Publishing Corporation http://www.hindawi.com