اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدGraphs with at most two trees in a forest building process
133
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Given a graph, we can form a spanning forest by first sorting the edges in some order, and then only keep edges incident to a vertex which is not incident to any previous edge. The resulting forest is dependent on the ordering of the edges, and so we can ask, for example, how likely is it for the process to produce a graph with $k$ trees. We look at all graphs which can produce at most two trees in this process and determine the probabilities of having either one or two trees. From this we construct infinite families of graphs which are non-isomorphic but produce the same probabilities.
قيم البحث
اقرأ أيضاً
A signed graph is a pair $(G,Sigma)$, where $G=(V,E)$ is a graph (in which parallel edges are permitted, but loops are not) with $V={1,ldots,n}$ and $Sigmasubseteq E$. The edges in $Sigma$ are called odd and the other edges of $E$ even. By $S(G,Sigma
)$ we denote the set of all symmetric $ntimes n$ matrices $A=[a_{i,j}]$ with $a_{i,j}<0$ if $i$ and $j$ are adjacent and connected by only even edges, $a_{i,j}>0$ if $i$ and $j$ are adjacent and connected by only odd edges, $a_{i,j}in mathbb{R}$ if $i$ and $j$ are connected by both even and odd edges, $a_{i,j}=0$ if $i ot=j$ and $i$ and $j$ are non-adjacent, and $a_{i,i} in mathbb{R}$ for all vertices $i$. The parameters $M(G,Sigma)$ and $xi(G,Sigma)$ of a signed graph $(G,Sigma)$ are the largest nullity of any matrix $Ain S(G,Sigma)$ and the largest nullity of any matrix $Ain S(G,Sigma)$ that has the Strong Arnold Hypothesis, respectively. In a previous paper, we gave a characterization of signed graphs $(G,Sigma)$ with $M(G,Sigma)leq 1$ and of signed graphs with $xi(G,Sigma)leq 1$. In this paper, we characterize the $2$-connected signed graphs $(G,Sigma)$ with $M(G,Sigma)leq 2$ and the $2$-connected signed graphs $(G,Sigma)$ with $xi(G,Sigma)leq 2$.
In his survey Beyond graph energy: Norms of graphs and matrices (2016), Nikiforov proposed two problems concerning characterizing the graphs that attain equality in a lower bound and in a upper bound for the energy of a graph, respectively. We show t
hat these graphs have at most two nonzero distinct absolute eigenvalues and investigate the proposed problems organizing our study according to the type of spectrum they can have. In most cases all graphs are characterized. Infinite families of graphs are given otherwise. We also show that all graphs satifying the properties required in the problems are integral, except for complete bipartite graphs $K_{p,q}$ and disconnected graphs with a connected component $K_{p,q}$, where $pq$ is not a perfect square.
We present the first steps towards the determination of the signed graphs for which the adjacency matrix has all but at most two eigenvalues equal to 1 or -1. Here we deal with the disconnected, the bipartite and the complete signed graphs. In additi
on, we present many examples which cannot be obtained from an unsigned graph or its negative by switching.
Let $G$ be an $n$-vertex graph with adjacency matrix $A$, and $W=[e,Ae,ldots,A^{n-1}e]$ be the walk matrix of $G$, where $e$ is the all-one vector. In Wang [J. Combin. Theory, Ser. B, 122 (2017): 438-451], the author showed that any graph $G$ is uniq
uely determined by its generalized spectrum (DGS) whenever $2^{-lfloor n/2 rfloor}det W$ is odd and square-free. In this paper, we introduce a large family of graphs $mathcal{F}_n={$ $n$-vertex graphs $Gcolon, 2^{-lfloor n/2 rfloor}det W =p^2b$ and rank$W=n-1$ over $mathbb{Z}/pmathbb{Z}},$ where $b$ is odd and square-free, $p$ is an odd prime and $p mid b$. We prove that any graph in $mathcal{F}_n$ either is DGS or has exactly one generalized cospectral mate up to isomorphism. Moreover, we show that the problem of finding the generalized cospectral mate for a graph in $mathcal{F}_n$ is equivalent to that of generating an appropriate rational orthogonal matrix from a given integral vector. This equivalence essentially depends on an amazing property of graphs in terms of generalized spectra, which states that any symmetric integral matrix generalized cospectral with the adjacency matrix of some graph must be an adjacency matrix. Based on this equivalence, we develop an efficient algorithm to decide whether a given graph in $mathcal{F}_n$ is DGS and further to find the unique generalized cospectral mate when it is not. We give some experimental results on graphs with at most 20 vertices, which suggest that $mathcal{F}_n$ may have a positive density (nearly $3%$) and possibly almost all graphs in $mathcal{F}_n$ are DGS as $nrightarrow infty$. This gives a supporting evidence for Haemers conjecture that almost all graphs are determined by their spectra.
A graph is called $2K_2$-free if it does not contain two independent edges as an induced subgraph. Mou and Pasechnik conjectured that every $frac{3}{2}$-tough $2K_2$-free graph with at least three vertices has a spanning trail with maximum degree at
most $4$. In this paper, we confirm this conjecture. We also provide examples for all $t < frac{5}{4}$ of $t$-tough graphs that do not have a spanning trail with maximum degree at most $4$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
