Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Minimal rankings of the Cartesian product Kₙ ☐ Kₘ

Gilbert EyabiJobby JacobRenu C. LaskarDarren A. NarayanDan Pillone — 2012

Discussiones Mathematicae Graph Theory

For a graph G = (V, E), a function f:V(G) → 1,2, ...,k is a k-ranking if f(u) = f(v) implies that every u - v path contains a vertex w such that f(w) > f(u). A k-ranking is minimal if decreasing any label violates the definition of ranking. The arank number, ψ r ( G ) , of G is the maximum value of k such that G has a minimal k-ranking. We completely determine the arank number of the Cartesian product Kₙ ☐ Kₙ, and we investigate the arank number of Kₙ ☐ Kₘ where n > m.

Offensive alliances in graphs

A set S is an offensive alliance if for every vertex v in its boundary N(S)- S it holds that the majority of vertices in v's closed neighbourhood are in S. The offensive alliance number is the minimum cardinality of an offensive alliance. In this paper we explore the bounds on the offensive alliance and the strong offensive alliance numbers (where a strict majority is required). In particular, we show that the offensive alliance number is at most 2/3 the order and the strong offensive alliance number...

Page 1

Download Results (CSV)