ﻻ يوجد ملخص باللغة العربية
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.
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
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 s
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 gra
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),
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)})$, wh