PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 33 | 4 | 709-715
Tytuł artykułu

Bounds on the Signed 2-Independence Number in Graphs

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Let G be a finite and simple graph with vertex set V (G), and let f V (G) → {−1, 1} be a two-valued function. If ∑x∈N|v| f(x) ≤ 1 for each v ∈ V (G), where N[v] is the closed neighborhood of v, then f is a signed 2-independence function on G. The weight of a signed 2-independence function f is w(f) =∑v∈V (G) f(v). The maximum of weights w(f), taken over all signed 2-independence functions f on G, is the signed 2-independence number α2s(G) of G. In this work, we mainly present upper bounds on α2s(G), as for example α2s(G) ≤ n−2 [∆ (G)/2], and we prove the Nordhaus-Gaddum type inequality α2s (G) + α2s(G) ≤ n+1, where n is the order and ∆ (G) is the maximum degree of the graph G. Some of our theorems improve well-known results on the signed 2-independence number.
Wydawca
Rocznik
Tom
33
Numer
4
Strony
709-715
Opis fizyczny
Daty
wydano
2013-09-01
online
2013-10-15
Twórcy
Bibliografia
  • [1] J.E. Dunbar, S.T. Hedetniemi, M.A. Henning and P.J. Slater, Signed domination in graphs, in: Graph Theory, Combinatorics, and Applications (John Wiley and Sons, Inc. 1, 1995) 311-322.
  • [2] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).
  • [3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs, Advanced Topics (Marcel Dekker, Inc., New York, 1998).
  • [4] M.A. Henning, Signed 2-independence in graphs, Discrete Math. 250 (2002) 93-107. doi:10.1016/S0012-365X(01)00275-8[Crossref]
  • [5] E.F. Shan, M.Y. Sohn and L.Y. Kang, Upper bounds on signed 2-independence numbers of graphs, Ars Combin. 69 (2003) 229-239.
  • [6] P. Turán, On an extremal problem in graph theory, Math. Fiz. Lapok 48 (1941) 436-452.
  • [7] B. Zelinka, On signed 2-independence numbers of graphs, manuscript.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1686
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ć.