Skip to main navigation Skip to search Skip to main content

Histories in Path Graphs

Research output: Contribution to journal › Article › peer-review

Abstract

For a given graph G and a positive integer r the r-path graph, Pr (G), has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length r - 1, and their union forms either a cycle or a path of length r + 1 in G. Let Prk (G) be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of Prk (G). The k-history Pr- k (H) is a subgraph of G that is induced by all edges that take part in the recursive definition of H. We present some general properties of k-histories and give a complete characterization of graphs that are k-histories of vertices of 2-path graph operator.

Original languageEnglish
Pages (from-to)243-250
Number of pages8
JournalElectronic Notes in Discrete Mathematics
Volume28
DOIs
StatePublished - 1 Mar 2007

Keywords

  • graph dynamics
  • history
  • path-graph

Fingerprint

Dive into the research topics of 'Histories in Path Graphs'. Together they form a unique fingerprint.

Cite this