An Extremal Problem On Potentially $K_{r+1}-H$-graphic Sequences

Details An Extremal Problem On Potentially $K_{r+1}-H$-graphic Sequences An Extremal Problem On Potentially $K_{r+1}-H$-graphic Sequences

2006-03-11

arxiv.org/abs/math/0603265v4

Ars Combinatoria, 94(2010), 289-298.

Mathematics

Combinatorics

10 pages

Scientific paper

Let $K_k$, $C_k$, $T_k$, and $P_{k}$ denote a complete graph on $k$ vertices, a cycle on $k$ vertices, a tree on $k+1$ vertices, and a path on $k+1$ vertices, respectively. 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}$). A sequence $S$ is potentially $K_{m}-H$-graphical if it has a realization containing a $K_{m}-H$ as a subgraph. Let $\sigma(K_{m}-H, n)$ denote the smallest degree sum such that every $n$-term graphical sequence $S$ with $\sigma(S)\geq \sigma(K_{m}-H, n)$ is potentially $K_{m}-H$-graphical. In this paper, we determine the values of $\sigma (K_{r+1}-H, n)$ for $n\geq 4r+10, r\geq 3, r+1 \geq k \geq 4$ where $H$ is a graph on $k$ vertices which contains a tree on 4 vertices but not contains a cycle on 3 vertices. We also determine the values of $\sigma (K_{r+1}-P_2, n)$ for $n\geq 4r+8, r\geq 3$. There are a number of graphs on $k$ vertices which containing a tree on 4 vertices but not containing a cycle on 3 vertices (for example, the cycle on $k$ vertices, the tree on $k$ vertices, and the complete 2-partite graph on $k$ vertices, etc).

Affiliated with

Also associated with

No associations

Rating

An Extremal Problem On Potentially $K_{r+1}-H$-graphic Sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Extremal Problem On Potentially $K_{r+1}-H$-graphic Sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Extremal Problem On Potentially $K_{r+1}-H$-graphic Sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-532836