Biswajit Das

Biswajit Das, Ramesh Hariharasubramanian

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.

Biswajit Das, Shreemayee Bora

The seminal work by Mackey et al. in 2006 (reference [21] of the article) introduced vector spaces of matrix pencils, with the property that almost all the pencils in the spaces are strong linearizations of a given square regular matrix polynomial. This work was subsequently extended by De Terán et al. in 2009 (reference [5] of the article) to include the case of square singular matrix polynomials. We extend this work to non-square matrix polynomials by proposing similar vector spaces of rectangular matrix pencils that are equal to the ones introduced by Mackey et al. when the polynomial is square. Moreover, the properties of these vector spaces are similar to those in the article by De Terán et al. for the singular case. In particular, the complete eigenvalue problem associated with the matrix polynomial can be solved by using almost every matrix pencil from these spaces. Further, almost every pencil in these spaces can be trimmed to form many smaller pencils that are strong linearizations of the matrix polynomial which readily solve the complete eigenvalue problem for the polynomial. These linearizations are easier to construct and are often smaller than the Fiedler linearizations introduced by De Terán et al. in 2012 (reference [7] of the article). Further, the global backward error analysis by Dopico et al. in 2016 (reference [10] of the article) applied to these linearizations, shows that they provide a wide choice of linearizations with respect to which the complete polynomial eigenvalue problem can be solved in a globally backward stable manner.