Search

The degree matrix of a graph is the diagonal matrix with diagonal entries equal to the degrees of the vertices of $X$. If $X_1$ and $X_2$ are graphs with respective adjacency matrices $A_1$ and $A_2$ and degree matrices $D_1$ and $D_2$, we say that $X_1$ and $X_2$ are degree similar if there is an invertible real matrix $M$ such that $M^{-1}A_1M=A_2$ and $M^{-1}D_1M=D_2$. If graphs $X_1$ and $X_2$ are degree similar, then their adjacency matrices, Laplacian matrices, unsigned Laplacian matrices and normalized Laplacian matrices are similar. We first show that the converse is not true. Then, we provide a number of constructions of degree-similar graphs. Finally, we show that the matrices $A_1-\mu D_1$ and $A_2-\mu D_2$ are similar over the field of rational functions $\mathbb{Q}(\mu)$ if and only if the Smith normal forms of the matrices $tI-(A_1-\mu D_1)$ and $tI-(A_2-\mu D_2)$ are equal., Comment: 22 pages, 8 figures

Given a collection $\mathcal{G} =\{G_1,G_2,\dots,G_m\}$ of graphs on the common vertex set $V$ of size $n$, an $m$-edge graph $H$ on the same vertex set $V$ is transversal in $\mathcal{G}$ if there exists a bijection $\varphi :E(H)\rightarrow [m]$ such that $e \in E(G_{\varphi(e)})$ for all $e\in E(H)$. Denote $\delta(\mathcal{G}):=\operatorname*{min}\left\{\delta(G_i): i\in [m]\right\}$. In this paper, we first establish a minimum degree condition for the existence of transversal Hamilton paths in $\mathcal{G}$: if $n=m+1$ and $\delta(\mathcal{G})\geq \frac{n-1}{2}$, then $\mathcal{G}$ contains a transversal Hamilton path. This solves a problem proposed by [Li, Li and Li, J. Graph Theory, 2023]. As a continuation of the transversal version of Dirac's theorem [Joos and Kim, Bull. Lond. Math. Soc., 2020] and the stability result for transversal Hamilton cycles [Cheng and Staden, arXiv:2403.09913v1], our second result characterizes all graph collections with minimum degree at least $\frac{n}{2}-1$ and without transversal Hamilton cycles. We obtain an analogous result for transversal Hamilton paths. The proof is a combination of the stability result for transversal Hamilton paths or cycles, transversal blow-up lemma, along with some structural analysis., Comment: 33 pages, 10 figures

Let $M\circ N$ denote the Schur product of two matrices $M$ and $N$. A graph $X$ with adjacency matrix $A$ is walk regular if $A^k\circ I$ is a constant times $I$ for each $k\ge0$, and $X$ is 1-walk-regular if it is walk regular and $A^k\circ A$ is a constant times $A$ for each $k\ge0$. Assume $X$ is 1-walk regular. Here we show that by deleting an edge in $X$, or deleting edges of a graph inside a clique of $X$, we obtain families of graphs that are not necessarily isomorphic, but are cospectral with respect to four types of matrices: the adjacency matrix, Laplacian matrix, unsigned Laplacian matrix, and normalized Laplacian matrix. Furthermore, we show that removing edges of Laplacian cospectral graphs in cliques of a 1-walk regular graph results in Laplacian cospectral graphs; removing edges of unsigned Laplacian cospectral graphs whose complements are also cospectral with respect to the unsigned Laplacian in cliques of a 1-walk regular graph results in unsigned Laplacian cospectral graphs.

Let $\mathcal{F}$ denote a set of graphs. A graph $G$ is said to be $\mathcal{F}$-free if it does not contain any element of $\mathcal{F}$ as a subgraph. The Tur\'an number is the maximum possible number of edges in an $\mathcal{F}$-free graph with $n$ vertices. It is well known that classical Tur\'an type extremal problem aims to study the Tur\'an number of fixed graphs. In 2010, Nikiforov \cite{Nik2} proposed analogously a spectral Tur\'an type problem which asks to determine the maximum spectral radius of an $\mathcal{F}$-free graph with $n$ vertices. It attracts much attention and many such problems remained elusive open even after serious attempts, and so they are considered as one of the most intriguing problems in spectral extremal graph theory. It is interesting to consider another spectral Tur\'an type problem which asks to determine the maximum spectral radius of an $\mathcal{F}$-free graph with $m$ edges. Denote by $\mathcal{G}(m,\mathcal{F})$ the set of $\mathcal{F}$-free graphs with $m$ edges having no isolated vertices. Each of the graphs among $\mathcal{G}(m,\mathcal{F})$ having the largest spectral radius is called a maximal graph. Let $\theta_{p,q,r}$ be a theta graph formed by connecting two distinct vertices with three independent paths of length $p,q$ and $r,$ respectively (length refers to the number of edges). In this paper, we firstly determine the unique maximal graph among $\mathcal{G}(m,\theta_{1,2,3})$ and $\mathcal{G}(m,\theta_{1,2,4}),$ respectively. Then we determine all the maximal graphs among $\mathcal{G}(m,C_5)$ (resp. $\mathcal{G}(m,C_6)$) excluding the book graph. These results extend some earlier results., Comment: 34 pages

Given a graph $G$, the adjacency matrix and degree diagonal matrix of $G$ are denoted by $A(G)$ and $D(G)$, respectively. In 2017, Nikiforov \cite{0007} proposed the $A_{\alpha}$-matrix: $A_{\alpha}(G)=\alpha D(G)+(1-\alpha)A(G),$ where $\alpha\in [0, 1]$. The largest eigenvalue of this novel matrix is called the $A_\alpha$-index of $G$. In this paper, we characterize the graphs with minimum $A_\alpha$-index among $n$-vertex graphs with independence number $i$ for $\alpha\in[0,1)$, where $i=1,\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil,{\lfloor\frac{n}{2}\rfloor+1},n-3,n-2,n-1,$ whereas for $i=2$ we consider the same problem for $\alpha\in [0,\frac{3}{4}{]}.$ Furthermore, we determine the unique graph (resp. tree) on $n$ vertices with given independence number having the maximum $A_\alpha$-index with $\alpha\in[0,1)$, whereas for the $n$-vertex bipartite graphs with given independence number, we characterize the unique graph having the maximum $A_\alpha$-index with $\alpha\in[\frac{1}{2},1).$, Comment: 21 pages; 4 figures; It is accepted by Acta Math. Appl. Sin. Engl. Ser

It is well known that spectral Tur\'{a}n type problem is one of the most classical {problems} in graph theory. In this paper, we consider the spectral Tur\'{a}n type problem. Let $G$ be a graph and let $\mathcal{G}$ be a set of graphs, we say $G$ is \textit{$\mathcal{G}$-free} if $G$ does not contain any element of $\mathcal{G}$ as a subgraph. Denote by $\lambda_1$ and $\lambda_2$ the largest and the second largest eigenvalues of the adjacency matrix $A(G)$ of $G,$ respectively. In this paper we focus on the characterization of graphs without short odd cycles according to the adjacency eigenvalues of the graphs. Firstly, an upper bound on $\lambda_1^{2k}+\lambda_2^{2k}$ of $n$-vertex $\{C_3,C_5,\ldots,C_{2k+1}\}$-free graphs is established, where $k$ is a positive integer. All the corresponding extremal graphs are identified. Secondly, a sufficient condition for non-bipartite graphs containing an odd cycle of length at most $2k+1$ in terms of its spectral radius is given. At last, we characterize the unique graph having the maximum spectral radius among the set of $n$-vertex non-bipartite graphs with odd girth at least $2k+3,$ which solves an open problem proposed by Lin, Ning and Wu [Eigenvalues and triangles in graphs, Combin. Probab. Comput. 30 (2) (2021) 258-270]., Comment: 15 pages. It is accepted by Discrete Mathematics

Let $G$ be a graph on $n$ vertices, its adjacency matrix and degree diagonal matrix are denoted by $A(G)$ and $D(G)$, respectively. In 2017, Nikiforov \cite{0007} introduced the matrix $A_{\alpha}(G)=\alpha D(G)+(1-\alpha)A(G)$ for $\alpha\in [0, 1].$ The $A_\alpha$-spectrum of a graph $G$ consists of all the eigenvalues (including the multiplicities) of $A_\alpha(G).$ A graph $G$ is said to be determined by the generalized $A_{\alpha}$-spectrum (or, DGA$_\alpha$S for short) if whenever $H$ is a graph such that $H$ and $G$ share the same $A_{\alpha}$-spectrum and so do their complements, then $H$ is isomorphic to $G$. In this paper, when $\alpha$ is rational, we present a simple arithmetic condition for a graph being DGA$_\alpha$S. More precisely, put $A_{c_\alpha}:={c_\alpha}A_\alpha(G),$ here ${c_\alpha}$ is the smallest positive integer such that $A_{c_\alpha}$ is an integral matrix. Let $\tilde{W}_{{\alpha}}(G)=\left[{\bf 1},\frac{A_{c_\alpha}{\bf 1}}{c_\alpha},\ldots, \frac{A_{c_\alpha}^{n-1}{\bf 1}}{c_\alpha}\right]$, where ${\bf 1}$ denotes the all-ones vector. We prove that if $\frac{\det \tilde{W}_{{\alpha}}(G)}{2^{\lfloor\frac{n}{2}\rfloor}}$ is an odd and square-free integer and the rank of $\tilde{W}_{{\alpha}}(G)$ is full over $\mathbb{F}_p$ for each odd prime divisor $p$ of $c_\alpha$, then $G$ is DGA$_\alpha$S except for even $n$ and odd $c_\alpha\,(\geqslant 3)$. By our obtained results in this paper we may deduce the main results in \cite{0005} and \cite{0002}., Comment: 20 pages

The out-of-gas error occurs when smart contract programs are provided with inputs that cause excessive gas consumption, and would be easily exploited to make the DoS attack. Multiple approaches have been proposed to estimate the gas limit of a function in smart contracts to avoid such error. However, under estimation often happens when the contract is complicated. In this work, we propose V-Gas, which could automatically generate inputs that maximizes the gas cost and reduce the under estimation cases. V-Gas is designed based on feedback-directed mutational fuzz testing. First, V-Gas builds the gas weighted control flow graph (CFG) of functions in smart contracts. Then, V-Gas develops gas consumption guided selection and mutation strategies to generate the input that maximize the gas consumption. For evaluation, we implement V-Gas based on js-evm, a widely used ethereum virtual machine written in javascript, and conduct experiments on 736 real-world transactions recorded on Ethereum. 44.02\% of the transactions would have out-of-gas errors under the estimation results given by solc, means that the recorded real gas consumption for those recorded transactions is larger than the gas limit value estimated by solc. While V-Gas could reduce the under estimation ratio to 13.86\%. Furthermore, V-Gas has exposed 25 previously unknown out-of-gas vulnerabilities in those widely-used smart contracts, 5 of which have been assigned unique CVE identifiers in the US National Vulnerability Database.