Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-03-27
Abstract： Let f(n) be the maximum number of edges in a graph on n vertices in which no two cycles have the same length. Erd¨os raised the problem of determining f(n). Erd¨os conjectured that there exists a positive constant c such that ex(n, C2k) ≥ cn1+1/k. Haj´os conjecture that every simple even graph on n vertices can be decomposed into at most n/2 cycles. We present the problems, conjectures related to these problems and we summarize the know results. We do not think Haj´os conjecture is true.
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-03-27
Abstract： The set of all non-increasing nonnegative integers sequence π = (d(v1), d(v2), ..., d(vn)) is denoted by NSn. A sequence π ∈ NSn 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 π. The set of all graphic sequences in NSn is denoted by GSn. A graphical sequence π is potentially H-graphical if there is a realization of π containing H as a subgraph, while π is forcibly H-graphical if every realization of π contains H as a subgraph. Let Kk denote a complete graph on k vertices. Let Km −H be the graph obtained from Km by removing the edges set E(H) of the graph H (H is a subgraph of Km). This paper summarizes briefly some recent results on potentially Km −G-graphic sequences and give a useful classification for determining σ(H, n).
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-02-18
Abstract： Summary: "In this paper we consider a variation of the classical Turán-type extremal problems. Let $S$be an $n$-term graphical sequence, and $\sigma(S)$be the sum of the terms in $S$. Let $H$be a graph. The problem is to determine the smallest even $l$such that any $n$-term graphical sequence $S$having $\sigma(S)\geq l$has a realization containing $H$as a subgraph. Denote this value $l$by $\sigma(H,n)$. We show $\sigma(C_{2m+1},n)=m(2n-m-1)+2$, for $m\geq 3$, $n\geq 3m$; $\sigma(C_{2m+2},n)=m(2n-m-1)+4$, for $m\geq 3$, $n\geq 5m-2$.''
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-02-13
Abstract： 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}$). We use the symbol $Z_4$ to
denote $K_4-P_2.$ 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}-Z, n)$ for
$n\geq 5r+19, r+1 \geq k \geq 5,$ $j \geq 5$ where $Z$ is a graph on $k$
vertices and $j$ edges which
contains a graph $Z_4$ but
not contains a cycle on $4$ vertices. We also determine the values of
$\sigma (K_{r+1}-Z_4, n)$, $\sigma (K_{r+1}-(K_4-e), n)$,
$\sigma (K_{r+1}-K_4, n)$ for
$n\geq 5r+16, r\geq 4$.
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-02-13
Abstract： 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$.
Hits
YES
Hits
Downloads
Comment