论文标题
在具有最小第四邻接系数的图表上
On graphs having minimal fourth adjacency coefficient
论文作者
论文摘要
令$ g $为订单$ n $和邻接矩阵$ \ mathbf {a}（g）$的图形。 $ g $的邻接多项式定义为$ ϕ（g;λ）= det（λ\ mathbf {i} - \ Mathbf {a}（g））= \ sum_ {i = 0}^n \ mathbf {a_i}（a_i}（a_i}（g）λ^{n-i-i} $。此后，$ \ mathbf {a} _i（g）$称为$ i $ -th邻接系数为$ g $。用$ \ mathfrak {g} _ {n，m} $表示所有具有$ n $ vertices和$ m $ edge的连接图的集合。如果$ \ mathbf {a} _4（g）= min \ {\ mathbf {a} _4（h）| h \ in \ mathfrak {g} _ {g} _ {n，m} \ Mathfrak {g} _ {n，m} \} $称为最小$ 4 $ -SACHS编号，$ \ Mathfrak {g} _ {n，m} $，由$ \ bar {\ bar {\ mathbf {a}}} _ 4（a}} _ 4（\ mathfrak {\ mathfrak）在本文中，我们研究了$ \ mathbf {a} _4（g）$的值与其结构属性之间的关系。尤其是，我们对$ 4 $ -SACHS的最小图进行了结构性表征，表明每个$ 4 $ -SACHS最小值都包含一个差异图作为其跨度子图（请参见Theorem 8）。然后，对于$ n \ ge 4 $和$ n-1 \ le m \ le 2n-4 $，我们确定所有$ 4 $ -SACHS的最小值以及相应的最小$ 4 $ -SACHS编号$ \ bar {\ Mathbf {a} a}} _ 4（\ Mathfrak {g Mathfrak {G} _ {g} _ {n，m} $。
Let $G$ be a graph with order $n$ and adjacency matrix $\mathbf{A}(G)$. The adjacency polynomial of $G$ is defined as $ϕ(G;λ) =det(λ\mathbf{I}-\mathbf{A}(G))=\sum_{i=0}^n\mathbf{a_i}(G)λ^{n-i}$. Hereafter, $\mathbf{a}_i(G)$ is called the $i$-th adjacency coefficient of $G$. Denote by $\mathfrak{G}_{n,m}$ the set of all connected graphs having $n$ vertices and $m$ edges. A graph $G$ is said $4$-Sachs minimal if $$\mathbf{a}_4(G)=min\{\mathbf{a}_4(H)|H\in \mathfrak{G}_{n,m}\}.$$ The value $min\{\mathbf{a}_4(H)|H\in \mathfrak{G}_{n,m}\}$ is called the minimal $4$-Sachs number in $\mathfrak{G}_{n,m}$, denoted by $\bar{\mathbf{a}}_4(\mathfrak{G}_{n,m})$. In this paper, we study the relationship between the value $\mathbf{a}_4(G)$ and its structural properties. Especially, we give a structural characterization on $4$-Sachs minimal graphs, showing that each $4$-Sachs minimal graph contains a difference graph as its spanning subgraph (see Theorem 8). Then, for $n\ge 4$ and $n-1\le m\le 2n-4$, we determine all $4$-Sachs minimal graphs together with the corresponding minimal $4$-Sachs number $\bar{\mathbf{a}}_4(\mathfrak{G}_{n,m})$.
