## Abstract

A function f:F→ {-1,1} defined on the vertices of a graph G = (V,E) is a signed 2-independence function if the sum of its function values over any closed neighbourhood is at most one. That is, for every i>6 V, f(N[v]) < 1, where N[v] consists of v and every vertex adjacent to i>. The weight of a signed 2-independence function is f(V) -42f(u), over all vertices v £V. The signed 2-independence number of a graph G, denoted cCj(G), equals the maximum weight of a signed 2-independence function of G. In this paper, we establish upper i bounds for «j(G) in terms of the order and size of the graph, and we characterize the graphs attaining these bounds. For a tree T, upper and lower bounds for a](T) are established and the extremal graphs characterized. It is shown that a}(G) can be arbitrarily large negative even for a cubic graph G.

Original language | English |
---|---|

Pages (from-to) | 93-107 |

Number of pages | 15 |

Journal | Discrete Mathematics |

Volume | 250 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 6 May 2002 |

Externally published | Yes |

## Keywords

- Bounds
- Signed 2-independence function
- Trees

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics