论文标题
在具有最小第四邻接系数的两分图上
On bipartite graphs having minimal fourth adjacency coefficient
论文作者
论文摘要
令$ g $是一个简单的图形，订单$ n $和邻接矩阵$ \ mathbf {a}（g）$。令$ ϕ（g;λ）= \ det（λi-\ mathbf {a}（g））= \ sum_ {i = 0}^n \ mathbf {a} _i（g）λ^{n-i} $是$ g $ of $ \ mathbf = $ g $的特征性polynomial be $ \ mathbf {a} a} a} a} a}系数为$ g $。用$ \ mathfrak {b} _ {n，m} $表示所有具有$ n $ vertices和$ m $ edge的连接图的集合。如果$ \ mathbf {a} _4（g）= min \ {\ mathbf {a} _4（h）| h \ in \ mathfrak {b} _ {b} _ {b} _ {b} _ {n，m} \}。 $ min \ {\ mathbf {a} _4（h）| h \ in \ mathfrak {b} _ {n，m} \} $称为最小$ 4 $ -SACHS $ \ MATHFRAK中的$ 4 $ -SACHS number $ \ bar {\ mathbf {a}} _ 4（\ mathfrak {b} _ {n，m}）$。 \ vspace {2mm}对于任何给定的整数对$（n，m）$，我们在本文中调查了两部分最佳图。首先，我们表明每个两部分最佳图是一个差异图（请参见定理10）。然后，我们在两部分最佳图上推断出一些结构特性。作为这些属性的应用程序，我们确定所有两部分最佳$（n，m）$ - 图形以及相应的最小$ 4 $ -SACHS编号，$ n \ ge 5 $和$ n-1 \ le m \ le m \ le 3（n-3）$。最后，我们表达了计算最小$ 4 $ -SACHS数字作为一类组合优化问题的问题，该问题与正整数的分区有关。
Let $G$ be a simple graph with order $n$ and adjacency matrix $\mathbf{A}(G)$. Let $ϕ(G; λ)=\det(λI-\mathbf{A}(G))=\sum_{i=0}^n\mathbf{a}_i(G)λ^{n-i}$ be the characteristic polynomial of $G$, where $\mathbf{a}_i(G)$ is called the $i$-th adjacency coefficient of $G$. Denote by $\mathfrak{B}_{n,m}$ the set of all connected graphs having $n$ vertices and $m$ edges. A bipartite graph $G$ is referred as bipartite optimal if $$\mathbf{a}_4(G)=min\{\mathbf{a}_4(H)|H\in \mathfrak{B}_{n,m}\}.$$ The value $min\{\mathbf{a}_4(H)|H\in \mathfrak{B}_{n,m}\}$ is called the minimal $4$-Sachs number in $\mathfrak{B}_{n,m}$, denoted by $\bar{\mathbf{a}}_4(\mathfrak{B}_{n,m})$. \vspace{2mm} For any given integer pair $(n,m)$, we in this paper investigate the bipartite optimal graphs. Firstly, we show that each bipartite optimal graph is a difference graph (see Theorem 10). Then we deduce some structural properties on bipartite optimal graphs. As applications of those properties, we determine all bipartite optimal $(n,m)$-graphs together with the corresponding minimal $4$-Sachs number for $n\ge 5$ and $n-1\le m\le 3(n-3)$. Finally, we express the problem of computing the minimal $4$-Sachs number as a class of combinatorial optimization problem, which relates to the partitions of positive integers.
