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 Eyabi;  Jobby Jacob;  Renu C. Laskar;  Darren A. Narayan;  Dan 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

Odile Favaron;  Gerd Fricke;  Wayne Goddard;  Sandra M. Hedetniemi;  Stephen T. Hedetniemi;  Petter Kristiansen;  Renu C. Laskar;  R. Duane Skaggs — 2004

Discussiones Mathematicae Graph Theory

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)