MathDB

2

Part of 2015 IMAR Test

Problems(1)

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

Source: IMAR 2015 p2

9/27/2018
Let nn be a positive integer and let GnG_n be the set of all simple graphs on nn vertices. For each vertex vv of a graph in GnG_n, let k(v)k(v) be the maximal cardinality of an independent set of neighbours of vv. Determine maxG∈GnΣv∈V(G)k(v)max_{G \in G_n} \Sigma_{v\in V (G)}k(v) and the graphs in GnG_n that achieve this value.
graphgraph theoryMaximalVerticescombinatorics