Word-Representable Co-Bipartite Graphs: Vertex Ordering, Representation Number, Speed, and Entropy

Abstract

A graph $G(V,E)$ is word-representable if there exists a word $w$ over the alphabet $V$ such that for distinct letters $x,y\in V$, $x$ and $y$ alternate in $w$ if and only if they are adjacent in $G$. In general, determining whether a graph is word-representable is an NP-complete problem. A graph is co-bipartite if its complement is bipartite. Therefore, the vertex set of a co-bipartite graph can be partitioned into two disjoint subsets $X$ and $Y$ such that the subgraphs induced by $X$ and $Y$ are cliques. In this paper, we obtain necessary and sufficient conditions for a co-bipartite graph to be word-representable in terms of a vertex ordering. Based on this ordering, we study the representation number of word-representable co-bipartite graphs and analyse the speed and entropy of this graph class. We show that the representation number of any word-representable co-bipartite graph is at most $3$, and that permutation graphs are the only co-bipartite graphs with representation number $2$. We prove that the speed is $2^{O(n\log n)}$ and the entropy is $0$. This provides an asymptotic bound on the number of labelled graphs in this class, which is significantly smaller than the known bound for the class of all co-bipartite graphs. These results provide a better understanding of the structure and enumeration of word-representable co-bipartite graphs and show that vertex ordering is an effective tool for studying this class.