UP - logo
E-resources
Full text
Peer reviewed
  • On Bipartite Graphs Having ...
    Gong, Shi-Cai; Zhang, Li-Ping; Sun, Shao-Wei

    Graphs and combinatorics, 06/2022, Volume: 38, Issue: 3
    Journal Article

    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).