PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 33 | 2 | 395-410
Tytuł artykułu

A Characterization of Trees for a New Lower Bound on the K-Independence Number

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Let k be a positive integer and G = (V,E) a graph of order n. A subset S of V is a k-independent set of G if the maximum degree of the subgraph induced by the vertices of S is less or equal to k − 1. The maximum cardinality of a k-independent set of G is the k-independence number βk(G). In this paper, we show that for every graph [xxx], where χ(G), s(G) and Lv are the chromatic number, the number of supports vertices and the number of leaves neighbors of v, in the graph G, respectively. Moreover, we characterize extremal trees attaining these bounds.
Słowa kluczowe
Wydawca
Rocznik
Tom
33
Numer
2
Strony
395-410
Opis fizyczny
Daty
wydano
2013-05-01
online
2013-04-13
Twórcy
  • LAMDA-RO, Department of Mathematics University of Blida B.P. 270, Blida, Algeria, meddahn11@yahoo.fr
  • LAMDA-RO, Department of Mathematics University of Blida B.P. 270, Blida, Algeria, mblidia@hotmail.com
Bibliografia
  • [1] S.T. Hedetniemi, Hereditary properties of graphs, J. Combin. Theory (B) 14 (1973) 94-99. doi:10.1016/S0095-8956(73)80009-7[Crossref]
  • [2] M. Blidia, M. Chellali, O. Favaron and N. Meddah, On k-independence in graphs with emphasis on trees, Discrete Math. 307 (2007) 2209-2216. doi:10.1016/j.disc.2006.11.007[Crossref]
  • [3] M. Borowiecki and D. Michalak, Generalized independence and domination in graphs, Discrete Math. 191 (1998) 51-56. doi:10.1016/S0012-365X(98)00092-2[Crossref]
  • [4] R.L. Brooks, On coloring the nodes of a network, Math. Proc. Cambridge Philos. Soc. 37 (1941) 194-197. doi:10.1017/S030500410002168X[Crossref]
  • [5] Y. Caro and Z. Tuza, Improved lower bounds on k-independence, J. Graph Theory 15 (1991) 99-107. doi:10.1002/jgt.3190150110[Crossref]
  • [6] O. Favaron, k-domination and k-independence in graphs, Ars Combin. 25 (1988) 159-167.
  • [7] O. Favaron, On a conjecture of Fink and Jacobson concerning k-domination and k-dependence, J. Combin. Theory (B) 39 (1985) 101-102. doi:10.1016/0095-8956(85)90040-1[Crossref]
  • [8] J.F. Fink and M.S. Jacobson, n-domination in graphs, in: Graph Theory with Applications to Algorithms and Computer Science, John Wiley and Sons, New York (1985) 283-300.
  • [9] J.F. Fink and M.S. Jacobson, n-domination, n-dependence and forbidden subgraphs, in: Graph Theory with Applications to Algorithms and Computer Science, John Wiley and Sons, New York (1985) 301-311.
  • [10] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).
  • [11] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, Inc., New York, 1998).
  • [12] L. Volkmann, A characterization of bipartite graphs with independence number half their order , Australas. J. Combin. 41 (2008) 219-222.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1677
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.