On Bipartite Graphs Having Minimum Fourth Adjacency Coefficient

Let G be a simple graph with order n and adjacency matrix A ( G ) . The characteristic polynomial of G is defined by ϕ ( G ; λ ) = det ( λ I - A ( G ) ) = ∑ i = 0 n a i ( G ) λ n - i , where a i ( G ) is called the i -th adjacency coefficient of G . Denote by B n , m the collection of all connected...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2022-06, Vol.38 (3), Article 60
Main Authors: Gong, Shi-Cai, Zhang, Li-Ping, Sun, Shao-Wei
Format: Article
Language:English
Subjects:
Apexes
Codes
Combinatorics
Engineering Design
Graph theory
Graphs
Mathematics
Mathematics and Statistics
Original Paper
Polynomials
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G be a simple graph with order n and adjacency matrix A ( G ) . The characteristic polynomial of G is defined by ϕ ( G ; λ ) = det ( λ I - A ( G ) ) = ∑ i = 0 n a i ( G ) λ n - i , where a i ( G ) is called the i -th adjacency coefficient of G . Denote by B n , m the collection of all connected bipartite graphs having n vertices and m edges. A bipartite graph G is referred as 4-Sachs optimal if a 4 ( G ) = min { a 4 ( H ) ∣ H ∈ B n , m } . For any given integer pair ( n ,  m ), in this paper we investigate the 4-Sachs optimal bipartite graphs. Firstly, we show that each 4-Sachs optimal bipartite graph is a difference graph. Then we deduce some structural properties on 4-Sachs optimal bipartite graphs. Especially, we determine the unique 4-Sachs optimal bipartite ( n ,  m )-graphs for n ≥ 5 and n - 1 ≤ m ≤ 2 ( n - 2 ) . Finally, we provide a method to construct a class of cospectral difference graphs, which disprove a conjecture posed by Andelić et al. (J Czech Math 70:1125–1138, 2020).
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-022-02461-7