NDLI: Hamiltonicity and cycle extensions in 0-block-intersection graphs of balanced incomplete block designs

Content Provider	Springer Nature Link
Author	Poulin, Jonathan LeGrow, Jason T. Pike, David A.
Copyright Year	2015
Abstract	A cycle $$\mathscr {C}$$ in a graph $$G$$ is called extendable if there is another cycle in $$G$$ which contains all the vertices of $$\mathscr {C}$$ and exactly one other vertex. A graph $$G$$ is cycle extendable if all its non-Hamilton cycles are extendable. A balanced incomplete block design with parameters $$v$$ , $$k$$ , and $$\lambda $$ , written BIBD $$ (v, k, \lambda ) $$ , is a pair $$\mathscr {D}= (V, \mathscr {B})$$ of sets, where $$V$$ is a set of $$v$$ elements and $$\mathscr {B}$$ is a set of $$k$$ -subsets of $$V$$ —called blocks—such that each pair of elements of $$V$$ appears in exactly $$\lambda $$ blocks in $$\mathscr {B}$$ . The 0-block-intersection graph of a design $$\mathscr {D}= (V, \mathscr {B})$$ is the graph $$\overline{G}_\mathscr {D}$$ whose vertex set is $$\mathscr {B}$$ and in which two blocks are adjacent if and only if they do not intersect. An $$A_1'$$ cyclic ordering of a BIBD $$ (v, k, \lambda )$$ is a listing of the elements of its block set such that consecutive blocks do not intersect and the last block does not intersect the first—such an ordering corresponds to a Hamilton cycle in the 0-block-intersection graph of the design and to a 0-intersecting Gray code for the design, and vice versa. In this paper we demonstrate that if $$\overline{G}_\mathscr {D}$$ is the 0-block-intersection graph of $$\mathscr {D}$$ , a BIBD $$ (v, k, \lambda )$$ , then $$\overline{G}_\mathscr {D}$$ is Hamiltonian if $$\lambda =1$$ and $$v > \left( \frac{1+\sqrt{5}}{2}\right) k^2+k$$ , and cycle extendable if $$v > 2k^2+1$$ . We also present a polynomial-time algorithm for finding cycles of any length in the 0-block-intersection graph of a BIBD $$ (v, k, \lambda ) $$ with $$v > (2+\sqrt{3})k^2+1$$ if $$\lambda =1$$ or $$v > 5k^2+1$$ if $$\lambda \geqslant 2$$ .
Ending Page	433
Page Count	13
Starting Page	421
File Format	PDF
ISSN	09251022
e-ISSN	15737586
Journal	Designs, Codes and Cryptography
Issue Number	3
Volume Number	80
Language	English
Publisher	Springer US
Publisher Date	2015-07-18
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Information and Communication, Circuits Cycle extendability Data Encryption Block-intersection graphs Eulerian and Hamiltonian graphs Data Structures, Cryptology and Information Theory Gray codes Hamilton cycles Discrete Mathematics in Computer Science Coding and Information Theory Block designs Graph algorithms Combinatorics Paths and cycles
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Discrete Mathematics and Combinatorics Theoretical Computer Science Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Hamilton cycles in restricted block-intersection graphs

Twofold triple systems without 2-intersecting Gray codes

A Degree Sum Condition for Hamiltonicity in Balanced Bipartite Digraphs

Degree and neighborhood intersection conditions restricted to induced subgraphs ensuring Hamiltonicity of graphs

The spurs of D. H. Lehmer : Hamiltonian paths in neighbor-swap graphs of permutations

Intersection of Longest Cycle and Largest Bond in 3-Connected Graphs

A degree sum condition for hamiltonicity in balanced bipartite digraphs

Hamiltonicity of 3-arc graphs

On dominating pair degree conditions for hamiltonicity in balanced bipartite digraphs

Hamiltonicity and cycle extensions in 0-block-intersection graphs of balanced incomplete block designs

Similar Documents

Hamilton cycles in restricted block-intersection graphs

Twofold triple systems without 2-intersecting Gray codes

A Degree Sum Condition for Hamiltonicity in Balanced Bipartite Digraphs

Degree and neighborhood intersection conditions restricted to induced subgraphs ensuring Hamiltonicity of graphs

The spurs of D. H. Lehmer : Hamiltonian paths in neighbor-swap graphs of permutations

Intersection of Longest Cycle and Largest Bond in 3-Connected Graphs

A degree sum condition for hamiltonicity in balanced bipartite digraphs

Hamiltonicity of 3-arc graphs

On dominating pair degree conditions for hamiltonicity in balanced bipartite digraphs

Hamiltonicity and cycle extensions in 0-block-intersection graphs of balanced incomplete block designs