Multicyclic treelike reflexive graphs |
| |
Authors: | Z Radosavljevi? M Rašajski |
| |
Institution: | Belgrade University, School of Electrical Engineering, Belgrade, Serbia |
| |
Abstract: | A simple graph is reflexive if its second largest eigenvalue does not exceed 2. A graph is treelike (sometimes also called a cactus) if all its cycles (circuits) are mutually edge-disjoint. In a lot of cases one can establish whether a given graph is reflexive by identifying and removing a single cut-vertex (Theorem 1). In this paper we prove that, if this theorem cannot be applied to a connected treelike reflexive graph G and if all its cycles do not have a common vertex (do not form a bundle), such a graph has at most five cycles (Theorem 2). On the same conditions, in Theorem 3 we find all maximal treelike reflexive graphs with four and five cycles. |
| |
Keywords: | Graph theory Second largest eigenvalue Treelike graphs |
本文献已被 ScienceDirect 等数据库收录! |