[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

The dynamics of the line and path graph operators

  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

For any integerk e 1 thek- path graph Pk (G) of a graph G has all length-k subpaths ofG as vertices, and two such vertices are adjacent whenever their union (as subgraphs ofG) forms a path or cycle withk + 1 edges. Fork = 1 we get the well-known line graphP 1 (G) =L(G). Iteratedk-path graphs Pt k(G) are defined as usual by Pt k (G) := Pk(P t−1 k(G)) ift < 1, and by P1 k(G): = Pk(G). A graph G isP k -periodic if it is isomorphic to some iteratedk-path graph of itself; itP k -converges if some iteratedk-path graph of G isP k -periodic. A graph has infiniteP k -depth if for any positive integert there is a graphH such that Pt k(H) ≃G. In this paperP k -periodic if it is isomorphic to some iteratedk-path graph of itself; itP k -converges if some iteratedk-path graph of G isP k -periodic graphs,P k -periodic if it is isomorphic to some iteratedk-path graph of itself; itP k -converges if some iteratedk-path graph of G isP k -convergent graphs, and graphs with infiniteP k -periodic if it is isomorphic to some iteratedk-path graph of itself; itP k -converges if some iteratedk-path graph of G isP k -depth are characterized inside some subclasses of the class of locally finite graphs fork = 1, 2.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Beineke, L.W.: Characterizations of derived graphs. J. Comb. Theory9, 129–135 (1970)

    Article  MATH  MathSciNet  Google Scholar 

  2. Broersma, H.J., Hoede, C.: Path graphs. J. Graph Theory13, 427–444 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  3. Ghirlanda, A.M.: Osservazioni sulle caratteristiche dei graft o singrammi. Ann. Univ. Ferrara Nuova Ser., Sez. VII11, 93–106 (1962-65)

    MathSciNet  Google Scholar 

  4. Ghirlanda, A.M.: Sui graft ftniti autocommutabili. Boll. Unione Mat. Ital. III Ser.18, 281–284(1963)

    MATH  Google Scholar 

  5. Jung, H.A.: Zu einem Isomorphiesatz von H. Whitney für Graphen. Math. Ann.164, 270–271 (1966)

    Article  MATH  MathSciNet  Google Scholar 

  6. Menon, V.V.: The isomorphism between graphs and their adjoint graphs. Can. Math. Bull.8, 7–15 (1965)

    MATH  MathSciNet  Google Scholar 

  7. Menon, V.V.: On repeated interchange graphs. Amer. Math. Monthly73, 986–989 (1966)

    Article  MATH  MathSciNet  Google Scholar 

  8. Menon, V.V.: On repeated interchange graphs II. J. Comb. Theory Ser. B11, 54–57 (1971)

    Article  MATH  MathSciNet  Google Scholar 

  9. Ore, O.: Theory of graphs: American Mathematics Society Providence, Rhode Island 1962

  10. Porcu, L.: Sui graft autocommutati. Inst. Lombardo Acad. Sci. Lett. Rend. A100, 665–677 (1966)

    MATH  MathSciNet  Google Scholar 

  11. Prisner, E.: Iterated graph-valued functions. Preprint TU Berlin No. 232 1989

  12. Prisner, E.: Graph dynamics. Monograph in preparation.

  13. Sabidussi, G.: Existenz and Struktur selbstadjungierter Graphen Beitäge zur Graphen- theorie, Beiträge zur Graphentheorie, (H. Sachs, H.-J. Voß, H. Walther ed.) pp. 121–125. Teubner, Leipzig 1968

    Google Scholar 

  14. Sabidussi, G.: Existence and structure of self-adjoint graphs. Math. Zeitschrift104, 257–280 (1968)

    Article  MATH  MathSciNet  Google Scholar 

  15. Schwartz, B.L.: On interchange graphs. Pacific J. Math.27, 393–396 (1968)

    MATH  MathSciNet  Google Scholar 

  16. Schwartz, B.L.: Infinite self-interchange graphs. Pacific J. Math.31, 497–504 (1969)

    MATH  MathSciNet  Google Scholar 

  17. Schwartz, B.L., Beineke, L.W.: Locally infinite self-interchange graphs. Proc. Amer. Math. Soc.27, 8–12 (1971)

    Article  MATH  MathSciNet  Google Scholar 

  18. Whitney, H.: Congruent graphs and the connectivity of graphs. Amer. J. Math.54, 150–168 (1932)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Mathematisches Seminar der Universität Hamburg, Bundesstraße 55, 2000, Hamburg 13, Germany

    Erich Prisner

Authors
  1. Erich Prisner
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Prisner, E. The dynamics of the line and path graph operators. Graphs and Combinatorics 9, 335–352 (1993). https://doi.org/10.1007/BF02988321

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02988321

Key words

Search

Navigation