Displaying similar documents to “The fundamental group of a locally finite graph with ends-a hyperfinite approach”

On the number of representations of an element in a polygonal Cayley graph

Gabriella Kuhn, Paolo M. Soardi (1987)

Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni

Similarity:

We compute explicitly the number of paths of given length joining two vertices of the Cayley graph of the free product of cyclic groups of order k.

Pₘ-saturated bipartite graphs with minimum size

Aneta Dudek, A. Paweł Wojda (2004)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is said to be H-saturated if G is H-free i.e., (G has no subgraph isomorphic to H) and adding any new edge to G creates a copy of H in G. In 1986 L. Kászonyi and Zs. Tuza considered the following problem: for given m and n find the minimum size sat(n;Pₘ) of Pₘ-saturated graph of order n. They gave the number sat(n;Pₘ) for n big enough. We deal with similar problem for bipartite graphs.

Decompositions of quadrangle-free planar graphs

Oleg V. Borodin, Anna O. Ivanova, Alexandr V. Kostochka, Naeem N. Sheikh (2009)

Discussiones Mathematicae Graph Theory

Similarity:

W. He et al. showed that a planar graph not containing 4-cycles can be decomposed into a forest and a graph with maximum degree at most 7. This degree restriction was improved to 6 by Borodin et al. We further lower this bound to 5 and show that it cannot be improved to 3.

Colouring of cycles in the de Bruijn graphs

Ewa Łazuka, Jerzy Żurawiecki (2000)

Discussiones Mathematicae Graph Theory

Similarity:

We show that the problem of finding the family of all so called the locally reducible factors in the binary de Bruijn graph of order k is equivalent to the problem of finding all colourings of edges in the binary de Bruijn graph of order k-1, where each vertex belongs to exactly two cycles of different colours. In this paper we define and study such colouring for the greater class of the de Bruijn graphs in order to define a class of so called regular factors, which is not so difficult...

One-Three Join: A Graph Operation and Its Consequences

M.A. Shalu, S. Devi Yamini (2017)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we introduce a graph operation, namely one-three join. We show that the graph G admits a one-three join if and only if either G is one of the basic graphs (bipartite, complement of bipartite, split graph) or G admits a constrained homogeneous set or a bipartite-join or a join. Next, we define ℳH as the class of all graphs generated from the induced subgraphs of an odd hole-free graph H that contains an odd anti-hole as an induced subgraph by using one-three join and co-join...

On the number of representations of an element in a polygonal Cayley graph

Gabriella Kuhn, Paolo M. Soardi (1987)

Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti

Similarity:

We compute explicitly the number of paths of given length joining two vertices of the Cayley graph of the free product of cyclic groups of order k.

Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs

Binlong Li, Hajo J. Broersma, Shenggui Zhang (2016)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is said to be 1-tough if for every vertex cut S of G, the number of components of G − S does not exceed |S|. Being 1-tough is an obvious necessary condition for a graph to be hamiltonian, but it is not sufficient in general. We study the problem of characterizing all graphs H such that every 1-tough H-free graph is hamiltonian. We almost obtain a complete solution to this problem, leaving H = K1 ∪ P4 as the only open case.