English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

An $H$-graph is one representable as the intersection graph of connectedsubgraphs of a suitable subdivision of a fixed graph $H$, introduced byBir\'{o}, Hujter and Tuza (1992). An $H$-graph is proper if the representingsubgraphs of $H$ can be chosen incomparable by the inclusion. In this paper, wefocus on the isomorphism problem for $S_d$-graphs and $T$-graphs, where $S_d$is the star with $d$ rays and $T$ is an arbitrary fixed tree.  Answering an open problem of Chaplick, T\"{o}pfer, Voborn\'{\i}k and Zeman(2016), we provide an FPT-time algorithm for testing isomorphism and computingthe automorphism group of $S_d$-graphs when parameterized by~$d$, whichinvolves the classical group-computing machinery by Furst, Hopcroft, and Luks(1980). We also show that the isomorphism problem of $S_d$-graphs is at leastas hard as the isomorphism problem of posets of bounded width, for which noefficient combinatorial-only algorithm is known to date. Then we extend ourapproach to an XP-time algorithm for isomorphism of $T$-graphs whenparameterized by the size of $T$. Lastly, we contribute a simple FPT-timecombinatorial algorithm for isomorphism testing in the special case of proper$S_d$- and $T$-graphs.

Efficient Isomorphism for $S_d$-graphs and $T$-graphs