Potentially K m — G-graphical sequences: A survey

Abstract: The set of all non-increasing nonnegative integers sequence

p i =

(

d (v_{1}),

d (v_{2}),

...,

d (v_{n})

) is denoted by

N S_{n}

. A sequence

p i i n N S_{n}

is said to be graphic if it is the degree sequence of a simple graph

G

on

n

vertices, and such a graph

G

is called a realization of

p i

. The set of all graphic sequences in

N S_{n}

is denoted by

G S_{n}

. A graphical sequence

p i

is potentially

H

-graphical if there is a realization of

p i

containing

H

as a subgraph, while

p i

is forcibly

H

-graphical if every realization of

p i

contains

H

as a subgraph. Let

K_{k}

denote a complete graph on

k

vertices. Let

K_{m} - H

be the graph obtained from

K_{m}

by removing the edges set

E (H)

of the graph

H

(

H

is a subgraph of

K_{m}

). This paper summarizes briefly some recent results on potentially

K_{m} - G

-graphic sequences and give a useful classification for determining

s i g m a (H, n)

.

Recommendations

Cites Work

Cited In (6)

This page was built for publication: Potentially K m — G-graphical sequences: A survey