Bounds on the Signed 2-Independence Number in Graphs

• Autorzy: Lutz Volkmann
• 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.

Słowa kluczowe

EN

bounds; signed 2-independence function; signed 2-independence number; Nordhaus-Gaddum type result

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2013
• Tom: 33
• Numer: 4
• Strony: 709-715

Daty

wydano

2013-09-01

online

2013-10-15

Twórcy

autor

Lutz Volkmann

• Lehrstuhl II für Mathematik RWTH-Aachen University 52056 Aachen, Germany

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.

Identyfikatory

DOI

10.7151/dmgt.1686