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-03-26
Abstract: 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}}.$
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-03-26
Abstract: In 1975, P. Erd {o}s proposed the problem of determining the
maximum number $f(n)$ of edges in a graph with $n$ vertices in which
any two cycles are of different
lengths. In this paper, it is proved that $$f(n) geq n+ frac{107}{3}t+ frac{7}{3}$$
for $t=1260r+169 , (r geq 1)$
and $n geq frac{2119}{4}t^{2}+87978t+ frac{15957}{4}$. Consequently,
$ liminf sb {n to infty} {f(n)-n over sqrt n} geq sqrt {2 +
frac{7654}{19071}},$ which is better than the previous bounds
$ sqrt 2$ Y. Shi, Discrete Math. 71(1988), 57-71 , $ sqrt {2.4}$
C. Lai, Australas. J. Combin. 27(2003), 101-105 .
The conjecture $ lim_{n rightarrow infty} {f(n)-n over sqrt n}= sqrt {2.4}$ is not true.
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-03-26
Abstract: In 1975, P. Erd H os proposed the problem of determining the maximum number $f(n)$ of edges in a graph with $n$ vertices in which any two cycles are of different lengths. The sequence $(c_1,c_2, cdots,c_n)$ is the cycle length distribution of a graph $G$ with $n$ vertices, where $c_i$ is the number of cycles of length $i$ in $G$. Let $f(a_1,a_2, cdots,$$a_n)$ denote the maximum possible number of edges in a graph which satisfies $c_i leq a_i$, where $a_i$ is a nonnegative integer. In 1991, Shi posed the problem of determining $f(a_1,a_2, cdots,a_n),$ which extended the problem due to Erd H os. It is clear that $f(n)=f(1,1, cdots,1)$.Let $g(n,m)=f(a_1,a_2, cdots,a_n),$ where $a_i=1$ if $i/m$ is an integer, and $a_i=0$ otherwise.It is clear that $f(n)=g(n,1)$.We prove that $ liminf sb {n to infty} {f(n)-n over sqrt n} geq sqrt {2 + frac{40}{99}},$ which is better than the previous bounds $ sqrt 2$ (Shi, 1988), and $ sqrt {2 + frac{7654}{19071}}$ (Lai, 2017).We show that $ liminf_{n rightarrow infty} {g(n,m)-n over sqrt frac{n}{m}} > sqrt {2.444},$ for all even integers $m$. We make the following conjecture:$ liminf sb {n to infty} {f(n)-n over sqrt n} > sqrt {2.444}.$ par
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-18
Abstract: 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.$$
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-02-18
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}-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)
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$.
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-02-10
Abstract: "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$.''
Subjects: Mathematics >> Algebra and Number Theory Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2023-12-04
Abstract: Let $A_n$ be the Nakayama algebra of type $A$ with quadratic Jacobson radical to be zero and $X_n$ be the Nakayama algebra of type $A$ with quadratic Jacobson radical to be zero. In this paper, we consider the k-tensor $A_n otimes X_n$ and the classification of the indecomposable modules over $A_n otimes X_n$. Moreover, we provide a counting formula to compute the number of isoclasses of indecomposable $A_n otimes X_n$ -modules.
Peer Review Status:Awaiting Review
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2022-04-19
Abstract:
"
Peer Review Status:Awaiting Review
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2022-03-18
Abstract:
Pascal's triangle is a mathematical triangle of combinatorial numbers, from which Fibonacci number sequence and golden ratio can be obtained. Similarly, silver ratio can be generated based on Pell number sequence. Recently, the relations between Pascal's triangle and maximum Deng entropy (MXDE) are studied and presented. A straightforward question arises: if we design a triangle based on MXDE, what will the associated number sequence and the limiting ratio be like? Hence, this paper proposes a Pascal-like triangle based on MXDE, called the maximum Deng entropy triangle (MDET). Besides, the number sequences based on MDET are investigated. Next, the general term for the MDET sequence is presented and the limiting ratio in MDET sequence is analyzed. We prove that the limiting ratio in the right MDET sequence converges to the silver ratio. Moreover, some examples are given to expound MDET and the MDET sequence.
Peer Review Status:Awaiting Review
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2017-12-22
Abstract: We focus on a circuit graph arrangement and its free resolution from algebraic and combinatorics. We detected the generators of the derivation module and findout a basis for a free resoltion. At last, we offer a combinatorial expression of the free resolution.
Peer Review Status:Awaiting Review