On 4-Sachs Optimal Graphs

Let G be a graph with order n and adjacency matrix A ( G ) . The adjacency polynomial of G is defined as ϕ ( G ; λ ) = det ( λ I - A ( G ) ) = ∑ i = 0 n a i ( G ) λ n - i . Here, a i ( G ) is referred as the i -th adjacency coefficient of G . We use G n , m to denote the set of all connected graphs...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2023-08, Vol.39 (4), Article 74
Main Authors: Gong, Shi-Cai, Wang, Jia-Xin, Sun, Shao-Wei
Format: Article
Language:English
Subjects:
Apexes
Combinatorics
Engineering Design
Graph theory
Graphs
Mathematics
Mathematics and Statistics
Original Paper
Polynomials
Structural analysis
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G be a graph with order n and adjacency matrix A ( G ) . The adjacency polynomial of G is defined as ϕ ( G ; λ ) = det ( λ I - A ( G ) ) = ∑ i = 0 n a i ( G ) λ n - i . Here, a i ( G ) is referred as the i -th adjacency coefficient of G . We use G n , m to denote the set of all connected graphs having n vertices and m edges. A graph G ∈ G n , m is said to be 4-Sachs optimal in G n , m if a 4 ( G ) = min { a 4 ( H ) | H ∈ G n , m } . The minimum 4-Sachs number in G n , m is denoted by a 4 ¯ ( G n , m ) , which is the value of min { a 4 ( H ) | H ∈ G n , m } . In this paper, we study the relationship between the value of a 4 ( G ) and the structural properties of G . Specially, we provide a structural characterization of 4-Sachs optimal graphs by showing that each 4-Sachs optimal graph in G n , m contains a connected difference graph as its spanning subgraph. Additionally, for n ≥ 4 and n - 1 ≤ m ≤ 2 n - 4 , we determine all 4-Sachs optimal graphs, along with their corresponding minimum 4-Sachs number a 4 ¯ ( G n , m ) .
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-023-02663-7