Maximizing the Index of Signed Complete Graphs Containing a Spanning Tree with <i>k</i> Pendant Vertices

Abstract

A signed graph Σ=(G,σ) consists of an underlying graph G=(V,E) with a sign function σ:E→{−1,1}. Let A(Σ) be the adjacency matrix of Σ and λ1(Σ) denote the largest eigenvalue (index) of Σ. Define (Kn,H−) as a signed complete graph whose negative edges induce a subgraph H. In this paper, we focus on the following question: which spanning tree T with a given number of pendant vertices makes the λ1(A(Σ)) of the unbalanced (Kn,T−) as large as possible? To answer the question, we characterize the extremal signed graph with maximum λ1(A(Σ)) among graphs of type (Kn,T−).

Keywords

• signed complete graph
• index
• pendant vertices
• spanning tree