On some classes of bivalent and trivalent planar graphs
Jorge Alencar, Jean-Guy Caputo, Leonardo de Lima, Arnaud Knippel · 2025
Read On some classes of bivalent and trivalent planar graphs by Jorge Alencar, Jean-Guy Caputo, Leonardo de Lima, Arnaud Knippel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-13199.txt.
Introduction
Jorge Alencar, Jean-Guy Caputo, Leonardo de Lima, and Arnaud Knippel classify special graphs in a 2025 mathematics paper. A graph here is a network of points and links. Some networks admit a neat pattern of values on their points, drawn only from a tiny set, tied to a key matrix of the network.
Such patterns matter for engineering, notably for systems that vibrate. The team work out which networks in four flat families carry the patterns. The families are trees, networks with one cycle, networks with two cycles, and cactus networks where cycles share at most one point. Their results give a clear map of when these rare patterns can occur, which helps engineers spot designs with the wanted behavior.
Catalog record
| CREATOR | Jorge Alencar, Jean-Guy Caputo, Leonardo de Lima, Arnaud Knippel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-13199
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On some classes of bivalent and trivalent planar graphs Jorge Alencar, Jean-Guy Caputo, Leonardo de Lima, Arnaud Knippel Abstract A graph is called bivalent or trivalent if there exists an eigenvector of the graph Laplacian composed from { − 1 , 1 } \{-1,1\} or { − 1 , 0 , 1 } \{-1,0,1\} , respectively. These bivalent and trivalent eigenvectors are important for engineering applications, in particular for vibrating systems. In this article, we determine the structure of bivalent and trivalent graphs in the following planar graph families: trees, unicyclic, bicyclic, and cactus. Keywords: Laplacian matrix, Laplacian eigenvector, Bivalent graph, Trivalent graph. MSC classification 2010: 05C50, 05C35 1 Introduction Let G=(V,E) be a connected graph with vertex set V=\{1,2,\ldots,n\}. The Laplacian matrix of G is given by L(G)=D-A, where D=diag(d_{1},\ldots,d_{n}) is the diagonal matrix with entries equal to the degree of each vertex i\in V denoted by d_{i} and A is the adjacency matrix. It is well-known that L(G) is symmetric, semidefinite positive and the smallest eigenvalue is equal to zero. The eigenvalues of L(G) can be arranged as \lambda_{1}=0\leq\lambda_{2}\cdots\leq\lambda_{n}. The eigenspace associated with an eigenvalue \lambda of L(G) is denoted by \mathcal{E}_{L}(\lambda)=\{\mathbf{x}\in\mathbb{R}^{n},\;\mathbf{x}\neq 0:L(G)\mathbf{x}=\lambda\mathbf{x}\}. The first eigenvalue \lambda_{1}=0 is associated to an eigenvector with equal entries; it’s multiplicity is the number of connected components of the graph [ 1 ] . Relating the eigenspace of a graph to its structural properties is an important topic of spectral graph theory, and there has been a growing interest in this subject in recent years. Eigenvectors of the graph Laplacian are also important in applications such as vibrations of chemical molecules [ 1 ] - [ 2 ] . In particular, eigenvectors with entries from sets \{-1,1\} and \{-1,0,1\} can lead to the concen- -tration of energy when nonlinearities are added to the model [ 3 ] , [ 4 ] . For all these reasons, we consider the following problem: P : Which connected graphs affording a Laplacian eigenvalue \lambda have eigenvectors with entries only from sets \{-1,1\} and \{-1,0,1\} ? Graphs with Laplacian or signless Laplacian eigenvector entries from the sets \{-1,1\} or \{-1,0,1\} have been studied in [ 5 ] , [ 6 ] , [ 7 ] , [ 8 ] and [ 9 ] . The problem above has also been adressed for the adjacency matrix A instead of the graph Laplacian. Akbari et al. in [ 10 ] proved that the null space of the adjacency matrix of every forest has a \{-1,0,1\} - basis. Sanders in [ 11 ] proved that for every cograph there exist bases of the eigenspaces for the eigenvalues 0 and -1 that consist only of vectors with entries from \{-1,0,1\}. Sander, Sander, and Kriesell [ 12 ] characterized all unicyclic graphs for which there exists a basis of the kernel that consists only of vectors with entries from \{-1,0,1\}. We recall the following Definition 1.1 . A bivalent (resp. trivalent) eigenvector of the graph Laplacian is composed of \{-1,+1\} (resp. \{-1,0,+1\} ). A graph affording a bivalent (resp. trivalent) eigenvector is termed bivalent (resp. trivalent). In this article, we answered the problem P by characterizing bivalent and trivalent graphs in some classical families of planar graphs. Planar graphs are of particular interest for many applications. In particular, we characterize bivalent and trivalent trees, unicyclic, bicyclic, and cactus graphs. Our results indicate that very restricted Laplacian eigenvalues ( \lambda\in\{1,2,3,4\} ) are associated with bivalent or trivalent eigenvectors in all studied families. The article is organized as follows. Section 2 presents preliminary results, in particular the edge principle by Merris [ 13 ] which will be useful for many of our proofs. We also characterize bivalent and trivalent graphs with a leaf. Section 3 characterizes bivalent and trivalent trees and unicyclic graphs. Building on these results, Section 4 identifies all bivalent and trivalent bicyclic graphs. We consider general multicyclic graphs in Section 5 and in particular we give a formula for the cyclomatic number c of regular bipartite graphs, showing which values of c are possible. We then characterize bivalent and trivalent cactus graphs. 2 Preliminaries We use the terminology vertices and nodes interchangeably as well as edges and links. Let \mathbf{v}=(v_{1},\ldots,v_{n})^{T} be an eigenvector of L(G), we recall the following. Definition 2.1 . A vertex j\in V is a soft node for an eigenvector v of the Laplacian of G if there exist a vertex j such that v_{j}=0 . In other cases, the vertex j is called a non-soft node. Definition 2.2 (Soft regular graph) . A graph is d -soft regular for an eigenvector \mathbf{v} of the Laplacian if every non-soft node for \mathbf{v} has the same degree d . Vertices i and j that have v_{i}=v_{j} are called equal nodes. An edge connecting equal nodes is called an equal link. The next result is the edge-principle due to Merris [ 13 ] . We use the following two important results from Merris and reformulate the statements. Theorem 2.3 ( Edge principle [ 13 ] ) . Let \mathbf{v} be an eigenvector of L(G) affording an eigenvalue \lambda . If v_{i}=v_{j} , then \mathbf{v} is an eigenvector of L(G^{\prime}) affording the eigenvalue \lambda , where G^{\prime} is the graph obtained from G by deleting or adding the edge e_{ij} depending whether the equal link e_{ij} is an edge of G or not. Theorem 2.4 (Extension of soft nodes, [ 13 ] ) . Connecting one or more soft nodes to an existing soft node of a graph does not change the eigenvalue. From [ 6 ] and [ 9 ] , we recall general characterizations of bivalent and trivalent graphs. Theorem 2.5 ( Bivalent graphs ) . The bivalent graphs are the regular bipartite graphs, and their extensions obtained by adding edges between nodes having the same value for a bivalent eigenvector. For trivalent graphs, we need the definition of Definition 2.6 (Hard degree) . The hard degree \bar{d}_{j} of a vertex j is the number of neighbors of j that are not zero. Theorem 2.7 ( Trivalent graphs ) . Let G be a graph with an eigenvector \mathbf{v} associated with Laplacian eigenvalue \lambda . Then G is trivalent without any equal links if and only if (i) for each vertex j valued 1 or -1, \lambda=d_{j}+\bar{d}_{j}, where d_{j},\bar{d}_{j} are respectively the degree and hard degree. (ii) Each soft vertex j is connected to the same number of vertices +1 and -1 . The path P_{2} has a bivalent eigenvector [-1,1]^{T} associated with \lambda=2. Notice that \cup_{i=1}^{k}P_{2} still has a bivalent eigenvector \mathbf{v}=[-1,1,\ldots,-1,1]^{T} associated with \lambda=2 . Connecting equal nodes related to \mathbf{v} generates a graph that has the same eigenvector \mathbf{v}=[-1,1,\ldots,-1,1]^{T} according to Theorem 2.3 . A similar analysis holds if the initial graph G is a star graph S_{2k+1} . In this case, we have \lambda=1 associated with \mathbf{v}=[0,-1,1,\ldots,-1,1]^{T}, where the soft node is the dominant vertex. To conclude, using theorem 2.3 we can obtain arbitrarily many graphs with eigenvalue \lambda=2 by connecting a number of P_{2} or graphs with eigenvalue \lambda=1 by connecting star graphs S_{2k+1} . We have the following new result which will be useful in the following proofs. Theorem 2.8 ( Graph