Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRepresenting split graphs by words
152
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
There is a long line of research in the literature dedicated to word-representable graphs, which generalize several important classes of graphs. However, not much is known about word-representability of split graphs, another important class of graphs. In this paper, we show that threshold graphs, a subclass of split graphs, are word-representable. Further, we prove a number of general theorems on word-representable split graphs, and use them to characterize computationally such graphs with cliques of size 5 in terms of 9 forbidden subgraphs, thus extending the known characterization for word-representable split graphs with cliques of size 4. Moreover, we use split graphs, and also provide an alternative solution, to show that gluing two word-representable graphs in any clique of size at least 2 may, or may not, result in a word-representable graph. The two surprisingly simple solutions provided by us answer a question that was open for about ten years.
rate research
Read More
A directed graph is semi-transitive if and only if it is acyclic and for any directed path $u_1rightarrow u_2rightarrow cdots rightarrow u_t$, $t geq 2$, either there is no edge from $u_1$ to $u_t$ or all edges $u_irightarrow u_j$ exist for $1 leq i < j leq t$. In this paper, we study semi-transitivity of families of directed split graphs obtained by iterations of morphisms applied to the adjacency matrices and giving in the limit infinite directed split graphs. A split graph is a graph in which the vertices can be partitioned into a clique and an independent set. We fully classify semi-transitive infinite directed split graphs when a morphism in question can involve any $ntimes m$ matrices over ${-1,0,1}$ with a single natural condition.
A graph is locally irregular if any pair of adjacent vertices have distinct degrees. A locally irregular decomposition of a graph $G$ is a decomposition $mathcal{D}$ of $G$ such that every subgraph $H in mathcal{D}$ is locally irregular. A graph is said to be decomposable if it admits a locally irregular decomposition. We prove that any decomposable split graph can be decomposed into at most three locally irregular subgraphs and we characterize all split graphs whose decomposition can be into one, two or three locally irregular subgraphs.
The notion of a $p$-Riordan graph generalizes that of a Riordan graph, which, in turn, generalizes the notions of a Pascal graph and a Toeplitz graph. In this paper we introduce the notion of a $p$-Riordan word, and show how to encode $p$-Riordan graphs by $p$-Riordan words. For special important cases of Riordan graphs (the case $p=2$) and oriented Riordan graphs (the case $p=3$) we provide alternative encodings in terms of pattern-avoiding permutations and certain balanced words, respectively. As a bi-product of our studies, we provide an alternative proof of a known enumerative result on closed walks in the cube.
A split graph is a graph whose vertices can be partitioned into a clique and a stable set. We investigate the combinatorial species of split graphs, providing species-theoretic generalizations of enumerative results due to Bina and Pv{r}ibil (2015), Cheng, Collins, and Trenk (2016), and Collins and Trenk (2018). In both the labeled and unlabeled cases, we give asymptotic results on the number of split graphs, of unbalanced split graphs, and of bicolored graphs, including proving the conjecture of Cheng, Collins, and Trenk (2016) that almost all split graphs are balanced.
Let $Gamma(G,S)$ denote the Cayley graph of a group $G$ with respect to a set $S subset G$. In this paper, we analyze the spectral properties of the Cayley graphs $mathcal{T}_{m,n,k} = Gamma(mathbb{Z}_m ltimes_k mathbb{Z}_n, {(pm 1,0),(0,pm 1)})$, where $m,n geq 3$ and $k^m equiv 1 pmod{n}$. We show that the adjacency matrix of $mathcal{T}_{m,n,k}$, upto relabeling, is a block circulant matrix, and we also obtain an explicit description of these blocks. By extending a result due to Walker-Mieghem to Hermitian matrices, we show that $mathcal{T}_{m,n,k}$ is not Ramanujan, when either $m > 8$, or $n geq 400$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
