اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRegular projections of graphs with at most three double points
166
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A generic immersion of a planar graph into the 2-space is said to be knotted if there does not exist a trivial embedding of the graph into the 3-space obtained by lifting the immersion with respect to the natural projection from the 3-space to the 2-space. In this paper we show that if a generic immersion of a planar graph is knotted then the number of double points of the immersion is more than or equal to three. To prove this, we also show that an embedding of a graph obtained from a generic immersion of the graph (does not need to be planar) with at most three double points is totally free if it contains neither a Hopf link nor a trefoil knot.
قيم البحث
اقرأ أيضاً
We show that the maximum number of triples on $n$~points, if no three triples span at most five points, is $(1pm o(1))n^2/5$. More generally, let $f^{(r)}(n;k,s)$ be the maximum number of edges of an $r$-uniform hypergraph on $n$~vertices not contain
ing a subgraph with $k$~vertices and $s$~edges. In 1973, Brown, ErdH{o}s and Sos conjectured that the limit $lim_{nto infty}n^{-2}f^{(3)}(n;k,k-2)$ exists for all~$k$. They proved this for $k=4$, where the limit is $1/6$ and the extremal examples are Steiner triple systems. We prove the conjecture for $k=5$ and show that the limit is~$1/5$. The upper bound is established via a simple optimisation problem. For the lower bound, we use approximate $H$-decompositions of~$K_n$ for a suitably defined graph~$H$.
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.
Introduced recently, an n-crossing is a singular point in a projection of a link at which n strands cross such that each strand travels straight through the crossing. We introduce the notion of an ubercrossing projection, a knot projection with a sin
gle n-crossing. Such a projection is necessarily composed of a collection of loops emanating from the crossing. We prove the surprising fact that all knots have a special type of ubercrossing projection, which we call a petal projection, in which no loops contain any others. The rigidity of this form allows all the information about the knot to be concentrated in a permutation corresponding to the levels at which the strands lie within the crossing. These ideas give rise to two new invariants for a knot K: the ubercrossing number u(K), and petal number p(K). These are the least number of loops in any ubercrossing or petal projection of K, respectively. We relate u(K) and p(K) to other knot invariants, and compute p(K) for several classes of knots, including all knots of nine or fewer crossings.
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.
Koolen et al. showed that if a graph with smallest eigenvalue at least $-3$ has large minimal valency, then it is $2$-integrable. In this paper, we will focus on the sesqui-regular graphs with smallest eigenvalue at least $-3$ and study their integrability.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
