Displaying similar documents to “On the basis number and the minimum cycle bases of the wreath product of some graphs i”

Minimal cycle bases of the lexicographic product of graphs

M.M.M. Jaradat (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A construction of minimum cycle bases of the lexicographic product of graphs is presented. Moreover, the length of a longest cycle of a minimal cycle basis is determined.

Circuit bases of strongly connected digraphs

Petra M. Gleiss, Josef Leydold, Peter F. Stadler (2003)

Discussiones Mathematicae Graph Theory

Similarity:

The cycle space of a strongly connected graph has a basis consisting of directed circuits. The concept of relevant circuits is introduced as a generalization of the relevant cycles in undirected graphs. A polynomial time algorithm for the computation of a minimum weight directed circuit basis is outlined.

Some crossing numbers of products of cycles

Marián Klešč (2005)

Discussiones Mathematicae Graph Theory

Similarity:

The exact values of crossing numbers of the Cartesian products of four special graphs of order five with cycles are given and, in addition, all known crossing numbers of Cartesian products of cycles with connected graphs on five vertices are summarized.

Cycle Double Covers of Infinite Planar Graphs

Mohammad Javaheri (2016)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we study the existence of cycle double covers for infinite planar graphs. We show that every infinite locally finite bridgeless k-indivisible graph with a 2-basis admits a cycle double cover.

An upper bound on the basis number of the powers of the complete graphs

Salar Y. Alsardary (2001)

Czechoslovak Mathematical Journal

Similarity:

The basis number of a graph G is defined by Schmeichel to be the least integer h such that G has an h -fold basis for its cycle space. MacLane showed that a graph is planar if and only if its basis number is ≤ 2 . Schmeichel proved that the basis number of the complete graph K n is at most 3 . We generalize the result of Schmeichel by showing that the basis number of the d -th power of K n is at most 2 d + 1 .

An upper bound of the basis number of the strong product of graphs

Mohammed M.M. Jaradat (2005)

Discussiones Mathematicae Graph Theory

Similarity:

The basis number of a graph G is defined to be the least integer d such that there is a basis B of the cycle space of G such that each edge of G is contained in at most d members of B. In this paper we give an upper bound of the basis number of the strong product of a graph with a bipartite graph and we show that this upper bound is the best possible.