Header menu link for other important links
X
Structural Properties of Word Representable Graphs
, K. Mahalingam
Published in Birkhauser Verlag AG
2016
Volume: 10
   
Issue: 2
Pages: 209 - 222
Abstract
Given a word w= w1w2⋯ wn of length n over an ordered alphabet Σ k, we construct a graph G(w) = (V(w) , E(w)) such that V(w) has n vertices labeled 1 , 2 , … , n and for i, j∈ V(w) , (i, j) ∈ E(w) if and only if wiwj is a scattered subword of w of the form atat + 1, at∈ Σ k, for some 1 ≤ t≤ k- 1 with the ordering at< at + 1. A graph is said to be Parikh word representable if there exists a word w over Σ k such that G= G(w). In this paper we characterize all Parikh word representable graphs over the binary alphabet in terms of chordal bipartite graphs. It is well known that the graph isomorphism (GI) problem for chordal bipartite graph is GI complete. The GI problem for a subclass of (6, 2) chordal bipartite graphs has been addressed. The notion of graph powers is a well studied topic in graph theory and its applications. We also investigate a bipartite analogue of graph powers of Parikh word representable graphs. In fact we show that for G(w), G(w) [3] is a complete bipartite graph, for any word w over binary alphabet. © 2016, Springer International Publishing.
About the journal
JournalMathematics in Computer Science
PublisherBirkhauser Verlag AG
ISSN16618270