Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGraphs of kei and their diameters
59
0
0.0
(
0
)
Authors
Matthew Ashford
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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$.
In this paper we compare the brushing number of a graph with the zero-forcing number of its line graph. We prove that the zero-forcing number of the line graph is an upper bound for the brushing number by constructing a brush configuration based on a zero-forcing set for the line graph. Using a similar construction, we also prove the conjecture that the zero-forcing number of a graph is no more than the zero-forcing number of its line graph; moreover we prove that the brushing number of a graph is no more than the brushing number of its line graph. All three bounds are shown to be tight.
The aim of the article is to understand the combinatorics of snake graphs by means of linear algebra. In particular, we apply Kasteleyns and Temperley--Fishers ideas about spectral properties of weighted adjacency matrices of planar bipartite graphs to snake graphs. First we focus on snake graphs whose set of turning vertices is monochromatic. We provide recursive sequences to compute the characteristic polynomials; they are indexed by the upper or the lower boundary of the graph and are determined by a neighbour count. As an application, we compute the characteristic polynomials for L-shaped snake graphs and staircases in terms of Fibonacci product polynomials. Next, we introduce a method to compute the characteristic polynomials as convergents of continued fractions. Finally, we show how to transform a snake graph with turning vertices of two colours into a graph with the same number of perfect matchings to which we can apply the results above.
Let $G_1$ and $G_2$ be two simple connected graphs. The invariant textit{coronal} of graph is used in order to determine the $alpha$-eigenvalues of four different types of graph equations that are $G_1 circ G_2, G_1lozenge G_1$ and the other two`s are $G_1 odot G_2$ and $G_1 circleddash G_2$ which are obtained using the $R$-graph of $G_1$. As an application we construct infinitely many pairs of non-isomorphic $alpha$-Isospectral graph.
For a given hypergraph, an orientation can be assigned to the vertex-edge incidences. This orientation is used to define the adjacency and Laplacian matrices. In addition to studying these matrices, several related structures are investigated including the incidence dual, the intersection graph (line graph), and the 2-section. A connection is then made between oriented hypergraphs and balanced incomplete block designs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
