Tight blocking sets in some maximum packings of K_n

DOI10.1016/J.DISC.2006.11.060MaRDI QIDQ2468030zbMATH OpenOpenAlexFDO

Authors Giovanni Lo Faro, Antoinette Tripodi, Yanxun Chang

Publication date 30 January 2008

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2006.11.060

zbMATH Keywords

\((\lambda K_n,G)\)-designedge-leave graphkitemaximum packingtight blocking settriple system

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Combinatorial aspects of packing and covering (05B40)

Review text

In a \((\lambda K_n,G)\) maximum packing (whose subgraphs are all morphic to \(G\)), a subset \(T\) of the vertex set \(X\) is called a blocking set if each subgraph contains a vertex in both \(T\) and \(X\setminus T\). Such a blocking set is called tight if the edge-leave graph of the maximum packing can be partitioned into corrected components \(L_1,L_2,\dots, L_a\), and the vertex set of ech \(L_i\) \((1\leq i\leq a)\) contains at least one point in both \(T\) and \(X\setminus T\). The authors consider 2 cases: where \(G= K_3\), and where \(G\) is the kite graph with 4 edges on 4 vertices. For \(G= K_3\), they show that a blocking set can exist only when either (1) \(n= 4\), \(\lambda\) is odd or (2) \(n= 5\), \(\lambda\in\{1,2,4\}\) or (3) \(n\in \{6,8\}\), \(\lambda= 1\), while a tight blocking set can exist only when either (1) \(n= 4\), \(\lambda\) is odd or (2) \(n= 5\), \(\lambda= 1\). When \(G\) is the kite graph, the authors show a tight blocking set \(T\) exists (for all \(n\), \(\lambda\) and all feasible edge leave graphs). They leave open the problem of determining all feasible numbers of points in \(T\) here (for given \(n\), \(\lambda\) and all feasible edge-leave graphs).

Recommendations

• TBSs in some minimum coverings
• Maximum packings of \(K_ n\) with copies of \(K_ 4-e\)
• scientific article; zbMATH DE number 3867360
• Maximum packing and minimum covering of the line graph of the complete graph with kite
• Maximum 2 3 grid-block packings of K_v

Cites work

• Blocking sets in designs with block size 4
• scientific article; zbMATH DE number 3981181 (Why is no real title available?)
• scientific article; zbMATH DE number 24832 (Why is no real title available?)
• scientific article; zbMATH DE number 91056 (Why is no real title available?)
• scientific article; zbMATH DE number 398960 (Why is no real title available?)
• scientific article; zbMATH DE number 825136 (Why is no real title available?)

Cited in

(9)

• TBSs in some minimum coverings
• The fine triangle intersections for maximum kite packings
• Group divisible packings and coverings with any minimum leave and minimum excess
• Blocking sets in \(G\)-designs and \(K_{3,3}\)-designs
• Minimum embedding of STSs into (K₃+e)-systems
• Blocking sets for cycles and paths designs
• Maximum packing and minimum covering of the line graph of the complete graph with kite
• Perfect blocking sets in \(P_3\)-designs
• Kite-group divisible packings and coverings with any minimum leave and minimum excess

This page was built for publication: Tight blocking sets in some maximum packings of \(\lambda K_n\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2468030)