分类： 数学 >> 离散数学和组合数学 提交时间： 2024-03-27
摘要： 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.
分类： 数学 >> 离散数学和组合数学 提交时间： 2024-03-27
摘要： 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).
分类： 数学 >> 离散数学和组合数学 提交时间： 2024-03-26
摘要： In 1975, P. Erd {o}s proposed the problem of determining the maximum number $f(n)$ of edges in a graph of $n$ vertices in which any two cycles are of different lengths. In this paper, it is proved that $$f(n) geq n+32t-1$$ for $t=27720r+169 , (r geq 1)$ and $n geq frac{6911}{16}t^{2}+ frac{514441}{8}t- frac{3309665}{16}$. Consequently, $ liminf sb {n to infty} {f(n)-n over sqrt n} geq sqrt {2 + {2562 over 6911}}.$
分类： 数学 >> 离散数学和组合数学 提交时间： 2024-03-26
摘要： In 1975,P.Erd {o}sproposedtheproblemofdeterminingthemaximumnumber$f(n)$ofedgesinagraphwith$n$verticesinwhichanytwocyclesareofdifferentlengths.Inthispaper,itisprovedthat$$f(n) geqn+ frac{107}{3}t+ frac{7}{3}$$for$t=1260r+169 , (r geq1)$and$n geq frac{2119}{4}t^{2}+87978t+ frac{15957}{4}$.Consequently,$ liminf sb{n to infty}{f(n)-n over sqrtn} geq sqrt{2+ frac{7654}{19071}},$whichisbetterthanthepreviousbounds$ sqrt2$ Y.Shi,DiscreteMath.71(1988),57-71 ,$ sqrt{2.4}$ C.Lai,Australas.J.Combin.27(2003),101-105 .Theconjecture$ lim_{n rightarrow infty}{f(n)-n over sqrtn}= sqrt{2.4}$isnottrue.
分类： 数学 >> 离散数学和组合数学 提交时间： 2024-03-26
摘要： 设f(n) 是没有等长圈的n个顶点的图的最大可能边数。确定f(n)的问题由Erdos在1975年提出。本文给出了f(n)的下界。
分类： 数学 >> 离散数学和组合数学 提交时间： 2024-02-18
摘要： Summary: In this paper we consider a variation of the classical Turn-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$.''
分类： 数学 >> 离散数学和组合数学 提交时间： 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.$$
分类： 数学 >> 离散数学和组合数学 提交时间： 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)
分类： 数学 >> 离散数学和组合数学 提交时间： 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$.
分类： 数学 >> 离散数学和组合数学 提交时间： 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$.
分类： 数学 >> 离散数学和组合数学 提交时间： 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$.''
分类： 数学 >> 代数与数论 分类： 数学 >> 离散数学和组合数学 提交时间： 2023-12-04
摘要： 令An是 2 次Jacobson根为零的A型Nakayama代数, Xn 是 2 次Jacobson根为零的 tilde{A}型Nakayama代数. 本文考虑了An与Xn的k-张量An tensor Xn上的不可分解模的分类问题, 并给出其在同构意义下的计数公式.
分类： 数学 >> 离散数学和组合数学 提交时间： 2022-04-19
摘要： 可分集 (PS) 与几乎可分集 (APS) 是组合设计理论中两类重要的组合构型, 与许多其它组合结构具有密切联系, 例如 Z-循环惠斯特竞赛图, 循环差阵, 不含邻点的循环平衡样本设计, 不交差族及光正交码等. 由于可分集与几乎可分集的要求比较严苛, 其存在性问题迄今远未解决. 本文针对 p7 (mod 8) 为素数的情形, 建立p2阶可分集与 p 阶几乎可分集的新构造方法, 给出两类组合构型存在性的若干新结果. 特别地, 对 p7 (mod 8) 的素数 p, 本文确定 p2阶PS的存在性, 给出特定条件下 p 阶APS的存在性和渐近存在性, 并得到 p
分类： 数学 >> 离散数学和组合数学 提交时间： 2022-03-18
摘要： 帕斯卡三角是二项式系数的三角形式，由它可以得到斐波那契数列和黄金比（约等于1.618）。一个问题是：帕斯卡三角中是否能得到白银比（约等于2.414）？本文首先基于最大邓熵的质量函数分布，建立了一个最大邓熵三角（MDET），这是一个类帕斯卡三角（Pascal-like triangle）。推导了MDET数列的通项公式，并分析了MDET数列中的极限比。经典的帕斯卡三角左右对称，通过对角加（Diagonal sum）只能得到一种数列斐波那契数列，其极限比为黄金比。与帕斯卡三角不同，本文所提出的MDET是非对称结构，通过右对角加与左对角加可以生成两种数列右MDET数列和左MDET数列。本文证明了右MDET数列中的极限比收敛于白银比，而左MDET数列中的极限比收敛于数值2。本文通过数值算例说明了所提出的MDET及其数列的性质。
分类： 数学 >> 离散数学和组合数学 提交时间： 2017-12-22
摘要： 本文利用代数和组合的相关理论对超平面配置理论的自由性做出了相关研究，给出圈图所对应的图配置的生成元和导模的具体形式，并以图论的形式对圈图配置的导模及其自由解做出相关的组合解 释.
点击量
通过
点击量
下载量
评论
待评议
