Indexing All Rooted Subgraphs of a Rooted Graph

• IMADA Tomoki

  Graduate School of Informatics, Kyoto University

• NAGAMOCHI Hiroshi

  Graduate School of Informatics, Kyoto University

Abstract

Let G be a connected graph in which we designate a vertex or a block (a biconnected component) as the center of G. For each cut-vertex v, let G_v be the connected subgraph induced from G by v and the vertices that will be separated from the center by removal of v, where v is designated as the root of G_v. We consider the set R of all such rooted subgraphs in G, and assign an integer, called an index, to each of the subgraphs so that two rooted subgraphs in R receive the same indices if and only if they are isomorphic under the constraint that their roots correspond each other. In this paper, assuming a procedure for computing a signature of each graph in a class G of biconnected graphs, we present a framework for computing indices to all rooted subgraphs of a graph G with a center which is composed of biconnected components from G. With this framework, we can find indices to all rooted subgraphs of a outerplanar graph with a center in linear time and space.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E95-D (3), 712-721, 2012

  The Institute of Electronics, Information and Communication Engineers

Keywords

• graph isomorphism
• index
• rooted graphs
• outerplanar graphs
• signature

Details

• CRID: 1390282679355127424
• NII Article ID: 10030611480
• NII Book ID: AA10826272
• DOI: 10.1587/transinf.e95.d.712
• BIBCODE: 2012IEITI..95..712I
• ISSN: 17451361
• ISSN: 09168532
• Web Site: http://www.jstage.jst.go.jp/article/transinf/E95.D/3/E95.D_3_712/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed