
doi: 10.1002/jcd.21328
AbstractA cycle C in a graph G is extendable if there is some other cycle in G that contains each vertex of C plus one additional vertex. A graph is cycle extendable if every non‐Hamilton cycle in the graph is extendable. A balanced incomplete block design, BIBD, consists of a set V of v elements and a block set of k‐subsets of V such that each 2‐subset of V occurs in exactly λ of the blocks of . The block‐intersection graph of a design is the graph having as its vertex set and such that two vertices of are adjacent if and only if their corresponding blocks have nonempty intersection. In this paper, we prove that the block‐intersection graph of any BIBD is cycle extendable. Furthermore, we present a polynomial time algorithm for constructing cycles of all possible lengths in a block‐intersection graph.
intersection graph, block design, polynomial time algorithm, Paths and cycles, cycle extension, Combinatorial aspects of block designs
intersection graph, block design, polynomial time algorithm, Paths and cycles, cycle extension, Combinatorial aspects of block designs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
