اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدConflict-free (vertex)-connection numbers of graphs with small diameters
72
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A path in an(a) edge(vertex)-colored graph is called a conflict-free path if there exists a color used on only one of its edges(vertices). An(A) edge(vertex)-colored graph is called conflict-free (vertex-)connected if for each pair of distinct vertices, there is a conflict-free path connecting them. For a connected graph $G$, the conflict-free (vertex-)connection number of $G$, denoted by $cfc(G)(text{or}~vcfc(G))$, is defined as the smallest number of colors that are required to make $G$ conflict-free (vertex-)connected. In this paper, we first give the exact value $cfc(T)$ for any tree $T$ with diameters $2,3$ and $4$. Based on this result, the conflict-free connection number is determined for any graph $G$ with $diam(G)leq 4$ except for those graphs $G$ with diameter $4$ and $h(G)=2$. In this case, we give some graphs with conflict-free connection number $2$ and $3$, respectively. For the conflict-free vertex-connection number, the exact value $vcfc(G)$ is determined for any graph $G$ with $diam(G)leq 4$.
قيم البحث
اقرأ أيضاً
A path in a vertex-colored graph is called emph{conflict free} if there is a color used on exactly one of its vertices. A vertex-colored graph is said to be emph{conflict-free vertex-connected} if any two vertices of the graph are connected by a conf
lict-free path. This paper investigates the question: For a connected graph $G$, what is the smallest number of colors needed in a vertex-coloring of $G$ in order to make $G$ conflict-free vertex-connected. As a result, we get that the answer is easy for $2$-connected graphs, and very difficult for connected graphs with more cut-vertices, including trees.
We estimate Ramsey numbers for bipartite graphs with small bandwidth and bounded maximum degree. In particular we determine asymptotically the two and three color Ramsey numbers for grid graphs. More generally, we determine asymptotically the two col
or Ramsey number for bipartite graphs with small bandwidth and bounded maximum degree and the three color Ramsey number for such graphs with the additional assumption that the bipartite graph is balanced.
An edge-coloured path is emph{rainbow} if all the edges have distinct colours. For a connected graph $G$, the emph{rainbow connection number} $rc(G)$ is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connect
ed by a rainbow path. Similarly, the emph{strong rainbow connection number} $src(G)$ is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by a rainbow geodesic (i.e., a path of shortest length). These two concepts of connectivity in graphs were introduced by Chartrand et al.~in 2008. Subsequently, vertex-colour
Let $Gamma$ denote a $Q$-polynomial distance-regular graph with vertex set $X$ and diameter $D$. Let $A$ denote the adjacency matrix of $Gamma$. Fix a base vertex $xin X$ and for $0 leq i leq D$ let $E^*_i=E^*_i(x)$ denote the projection matrix to th
e $i$th subconstituent space of $Gamma$ with respect to $x$. The Terwilliger algebra $T(x)$ of $Gamma$ with respect to $x$ is the semisimple subalgebra of $mathrm{Mat}_X(mathbb{C})$ generated by $A, E^*_0, E^*_1, ldots, E^*_D$. Remark that the isomorphism class of $T(x)$ depends on the choice of the base vertex $x$. We say $Gamma$ is pseudo-vertex-transitive whenever for any vertices $x,y in X$, the Terwilliger algebras $T(x)$ and $T(y)$ are isomorphic. In this paper we discuss pseudo-vertex transitivity for distance-regular graphs with diameter $Din {2,3,4}$. In the case of diameter $2$, a strongly regular graph $Gamma$ is thin, and $Gamma$ is pseudo-vertex-transitive if and only if every local graph of $Gamma$ has the same spectrum. In the case of diameter $3$, Taylor graphs are thin and pseudo-vertex-transitive. In the case of diameter $4$, antipodal tight graphs are thin and pseudo-vertex-transitive.
A kei on $[n]$ can be thought of as a set of maps $(f_x)_{x in [n]}$, where each $f_x$ is an involution on $[n]$ such that $(x)f_x = x$ for all $x$ and $f_{(x)f_y} = f_yf_xf_y$ for all $x$ and $y$. We can think of kei as loopless, edge-coloured multi
graphs on $[n]$ where we have an edge of colour $y$ between $x$ and $z$ if and only if $(x)f_y = z$; in this paper we show that any component of diameter $d$ in such a graph must have at least $2^d$ vertices and contain at least $2^{d-1}$ edges of the same colour. We also show that these bounds are tight for each value of $d$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
