Maximum oriented forcing number for complete graphs

Publication date 13 December 2019

Abstract: The maximum oriented

k

-forcing number of a simple graph

G

, written

M O F_{k} (G)

, is the maximum directed

k

-forcing number among all orientations of

G

. This invariant was recently introduced by Caro, Davila and Pepper in [CaroDavilaPepper], and in the current paper we study the special case where

G

is the complete graph with order

n

, denoted

K_{n}

. While

M O F_{k} (G)

is an invariant for the underlying simple graph

G

,

M O F_{k} (K_{n})

can also be interpreted as an interesting property for tournaments. Our main results further focus on the case when

k = 1

. These include a lower bound on

M O F (K_{n})

of roughly

f r a c 34 n

, and for

n g e 2

, a lower bound of

n - f r a c 2 n l o g_{2} (n)

. Along the way, we also consider various lower bounds on the maximum oriented

k

-forcing number for the closely related complete

q

-partite graphs.

Recommendations

Cited in

(4)

This page was built for publication: Maximum oriented forcing number for complete graphs