Development of Graphical Characteristics Data Base:GCDB. Graphical Characteristics of Multi-Layerd Cyclic Fence Graph.

Kayoko Hayashi, Shiori Fukuda, Umpei Nagashima, Haruo HosoyaJournal of Chemical Software 1999 · DOI

Abstract

Researchers have developed the Graphical Characteristics Data Base (GCDB), a web-based repository designed to catalog and compare the complex mathematical properties of graphs. The initial release focuses on over 330 "Multi-Layered Cyclic Fence Graphs" (MLCFGs), providing a centralized tool for chemical informaticians and graph theorists to analyze topological indices that were previously managed through tedious manual filing. The database stores 16 distinct characteristics, including adjacency matrices, topological indices, and spectral data, accessible via a WWW interface.

Introduction

In fields like theoretical chemistry and network science, the physical and chemical properties of a molecule are often dictated by its underlying structure, which can be represented as a mathematical graph. To identify or compare these structures, researchers calculate "graphical characteristics"—numerical values or polynomials like the Wiener number or Kekulé count. Historically, these data were stored in fragmented, individual files. As the number of possible graphs grows exponentially, comparing these characteristics manually becomes nearly impossible. The GCDB automates the storage and retrieval of these multi-dimensional mathematical signatures.

System Architecture and Methods

The GCDB system consists of three main components: a core database storing 16 types of characteristics, a CGI-based web interface for user queries (SEARCH, DISPLAY, LOOK), and a backend calculation program that computes mathematical properties before ingestion.

Step-by-step construction of a multi-layered graph structure.

The system specifically catalogs Multi-Layered Cyclic Fence Graphs (MLCFGs). These are constructed by stacking multiple cycle graphs ($C_{2n}$) into layers and connecting them according to specific periodic rules. These rules categorize the graphs into distinct families such as $E_{m,n}$, $F_{m,n}$, and $G_{m,n}$.

The MLCFG Dataset

The current database contains approximately 330 unique MLCFGs. For each graph, 16 parameters are recorded, ranging from basic statistics (vertex/edge counts) to complex polynomials (matching, characteristic, and distance polynomials) and spectral data (all eigenvalues).

Classification of MLCFG types $E_{m,n}$ and $F_{m,n}$ by layer count ($m$) and cycle size ($n$).

Key Insights and Applications

  • Chemical Relevance: MLCFGs are "cubic" (each vertex has degree three) and "bipartite," making them structurally analogous to graphite lattices. This makes the database a valuable tool for carbon nanostructure research.
  • Mathematical Properties: Some MLCFGs are "integral graphs," where all eigenvalues are integers—a property of significant interest in pure mathematics. Additionally, the characteristic and distance polynomials of these layered graphs often follow recurrence relations, allowing the properties of larger graphs to be predicted from smaller components.
  • Visual Verification: The database provides visual diagrams, crucial for verifying structural symmetry and "torus graph" properties (the ability to be drawn on a torus without crossing edges).

Future Work

Future developments for GCDB include full automation of the data ingestion pipeline and the implementation of parallel processing to handle the computational load of larger graphs. A primary goal is to create a "self-proliferating" database that automatically triggers calculations when a user queries a non-existent graph. Additionally, the authors plan to integrate isomorphism tools to identify mathematically identical graphs that may be stored under different names.

Summary updated

Abstract

グラフの特性量を集めたデータベース(Graphical Characteristics Data Base : GCDB)を開発した。GCDBにはグラフの名前、頂点数、頂点の次数、辺の数、隣接行列、トポロジカルインデックス、ケクレ数、非隣接数、Z'、マッチング多項式、距離多項式、Sz、ウイーナー数、n歩数、固有値という16種類の特性量とコメントおよびグラフの図が、蓄えられている。ユーザーインターフェイスは、WWWを用いる。現在Multi-Layerd Cyclic Fence Graph約330とその特性量をデータベース化し、お茶の水女子大学において仮公開を開始した。(http://www.sap.is.ocha.ac.jp/~hayasi/cgi-bin/gcdb.cgi)
BibTeX
@article{hayashi1999development,
  author = {Kayoko Hayashi and Shiori Fukuda and Umpei Nagashima and Haruo Hosoya},
  title = {{Development of Graphical Characteristics Data Base:GCDB. Graphical Characteristics of Multi-Layerd Cyclic Fence Graph.}},
  journal = {Journal of Chemical Software},
  year = {1999},
  doi = {10.2477/jchemsoft.5.137},
}
Figure