• The smallest degree sum that yields potentially $C_k$ -graphical sequences

    分类: 数学 >> 离散数学和组合数学 提交时间: 2024-02-18

    摘要: 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$.''
     

  • An old problem of Erdos: a graph without two cycles of the same length

    分类: 数学 >> 离散数学和组合数学 提交时间: 2024-02-18

    摘要: In 1975, P. Erdős proposed the problem of determining the maximum number $f(n)$ of edges in a graph on $n$ vertices in which any two cycles are of different lengths. Let $f^{\ast}(n)$ be the maximum number of edges in a simple graph on $n$ vertices in which any two cycles are of different lengths. Let $M_n$ be the set of simple graphs on $n$ vertices in which any two cycles are of different lengths and with the edges of $f^{\ast}(n)$. Let $mc(n)$ be the maximum cycle length for all $G \in M_n$. In this paper, it is proved that for $n$ sufficiently large, $mc(n)\leq \frac{15}{16}n$. We make the following conjecture: $$\lim_{n \rightarrow \infty} {mc(n)\over n}= 0.$$

  • On potentially $K_{r+1}-U$-graphical Sequences

    分类: 数学 >> 离散数学和组合数学 提交时间: 2024-02-18

    摘要: 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}-U, n)$ for $n\geq 5r+18, r+1 \geq k \geq 7,$ $j \geq 6$ where $U$ is a graph on $k$ vertices and $j$ edges which contains a graph $K_3 \bigcup P_3$ but not contains a cycle on 4 vertices and not contains $Z_4$. There are a number of graphs on $k$ vertices and $j$ edges which contains a graph $(K_{3} \bigcup P_{3})$ but not contains a cycle on 4 vertices and not contains $Z_4$. (for example, $C_3\bigcup C_{i_1} \bigcup C_{i_2} \bigcup >... \bigcup C_{i_p}$ $(i_j\neq 4, j=2,3,..., p, i_1 \geq 5)$, $C_3\bigcup P_{i_1} \bigcup P_{i_2} \bigcup ... \bigcup P_{i_p}$ $(i_1 \geq 3)$, $C_3\bigcup P_{i_1} \bigcup C_{i_2} \bigcup >... \bigcup C_{i_p}$ $(i_j\neq 4, j=2,3,..., p, i_1 \geq 3)$, etc)

  • The smallest degree sum that yields potentially $K_{r+1}-Z$-graphical Sequences

    分类: 数学 >> 离散数学和组合数学 提交时间: 2024-02-13

    摘要: 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$.

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

    分类: 数学 >> 离散数学和组合数学 提交时间: 2024-02-13

    摘要: 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$.

  • A note on potentially $K_4-e$ graphical sequences

    分类: 数学 >> 离散数学和组合数学 提交时间: 2024-02-10

    摘要: "A sequence $S$is potentially $K_4-e$graphical if it has a realization containing a $K_4-e$as a subgraph. Let $\sigma(K_4-e,n)$denote the smallest degree sum such that every $n$-term graphical sequence $S$with $\sigma(S)\geq\sigma(K_4-e,n)$is potentially $K_4-e$graphical. Gould, Jacobson, Lehel raised the problem of determining the value of $\sigma(K_4-e,n)$. In this paper, we prove that $\sigma(K_4-e,n)=2[(3n-1)/2]$for $n\geq7$and $n=4,5$, and $\sigma(K_4-e,6)=20$.''