MathDB

simple graphs, k(v) maximal cardinality of an independent set of neighbours of v

Source: IMAR 2015 p2

September 27, 2018

graphgraph theoryMaximalVerticescombinatorics

Problem Statement

Let

n

be a positive integer and let

G_n

be the set of all simple graphs on

n

vertices. For each vertex

v

of a graph in

G_n

, let

k(v)

be the maximal cardinality of an independent set of neighbours of

v

. Determine

max_{G \in G_n} \Sigma_{v\in V (G)}k(v)

and the graphs in

G_n

that achieve this value.