اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدStability of pair graphs
49
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We start up the study of the stability of general graph pairs. This notion is a generalization of the concept of the stability of graphs. We say that a pair of graphs $(Gamma,Sigma)$ is stable if $Aut(GammatimesSigma) cong Aut(Gamma)times Aut(Sigma)$ and unstable otherwise, where $GammatimesSigma$ is the direct product of $Gamma$ and $Sigma$. An unstable graph pair $(Gamma,Sigma)$ is said to be a nontrivially unstable graph pair if $Gamma$ and $Sigma$ are connected coprime graphs, at least one of them is non-bipartite, and each of them has the property that different vertices have distinct neighbourhoods. We obtain necessary conditions for a pair of graphs to be stable. We also give a characterization of a pair of graphs $(Gamma, Sigma)$ to be nontrivially unstable in the case when both graphs are connected and regular with coprime valencies and $Sigma$ is vertex-transitive. This characterization is given in terms of the $Sigma$-automorphisms of $Gamma$, which are a new concept introduced in this paper as a generalization of both automorphisms and two-fold automorphisms of a graph.
قيم البحث
اقرأ أيضاً
Let $X$ be a connected Cayley graph on an abelian group of odd order, such that no two distinct vertices of $X$ have exactly the same neighbours. We show that the direct product $X times K_2$ (also called the canonical double cover of $X$) has only t
he obvious automorphisms (namely, the ones that come from automorphisms of its factors $X$ and $K_2$). This means that $X$ is stable. The proof is short and elementary. The theory of direct products implies that $K_2$ can be replaced with members of a much more general family of connected graphs.
We extend the classical stability theorem of Erdos and Simonovits in two directions: first, we allow the order of the forbidden graph to grow as log of order of the host graph, and second, our extremal condition is on the spectral radius of the host graph.
We confirm the equitable $Delta$-coloring conjecture for interval graphs and establish the monotonicity of equitable colorability for them. We further obtain results on equitable colorability about square (or Cartesian) and cross (or direct) products of graphs.
Let $P_n$ and $C_n$ denote the path and cycle on $n$ vertices respectively. The dumbbell graph, denoted by $D_{p,k,q}$, is the graph obtained from two cycles $C_p$, $C_q$ and a path $P_{k+2}$ by identifying each pendant vertex of $P_{k+2}$ with a ver
tex of a cycle respectively. The theta graph, denoted by $Theta_{r,s,t}$, is the graph formed by joining two given vertices via three disjoint paths $P_{r}$, $P_{s}$ and $P_{t}$ respectively. In this paper, we prove that all dumbbell graphs as well as theta graphs are determined by their Laplacian spectra.
Graham and Pollak showed that the vertices of any graph $G$ can be addressed with $N$-tuples of three symbols, such that the distance between any two vertices may be easily determined from their addresses. An addressing is optimal if its length $N$ i
s minimum possible. In this paper, we determine an addressing of length $k(n-k)$ for the Johnson graphs $J(n,k)$ and we show that our addressing is optimal when $k=1$ or when $k=2, n=4,5,6$, but not when $n=6$ and $k=3$. We study the addressing problem as well as a variation of it in which the alphabet used has more than three symbols, for other graphs such as complete multipartite graphs and odd cycles. We also present computations describing the distribution of the minimum length of addressings for connected graphs with up to $10$ vertices. Motivated by these computations we settle a problem of Graham, showing that most graphs on $n$ vertices have an addressing of length at most $n-(2-o(1))log_2 n$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
