Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConflict-free (vertex)-connection numbers of graphs with small diameters
72
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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 conflict-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 color 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 connected 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 the $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 multigraphs 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$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
