On graphs having minimal fourth adjacency coefficient

Abstract

Let $G$ be a graph with order $n$ and adjacency matrix $\mathbf{A}(G)$. The adjacency polynomial of $G$ is defined as $\varphi (G;\lambda )=det(\lambda \mathbf{I}-\mathbf{A}(G))={\sum }_{i=0}^n{\mathbf{a}}_{\mathbf{i}}(G){\lambda }^{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})$.

17 pages