Pairwise balanced designs and sigma clique partitions

详细信息    查看全文

• 作者：Akbar Davoodi ; Ramin Javadi<sup> ; sup><sup>rjavadi@cc.iut.ac.ir" class="auth_mail" title="E-mail the corresponding authorsup> ; Behnaz Omoomi
• 关键词：Clique partition ; Pairwise balanced design ; Sigma clique partition number
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 May 2016
• 年：2016
• 卷：339
• 期：5
• 页码：1450-1458
• 全文大小：449 K

文摘

In this paper, we are interested in minimizing the sum of block sizes in a pairwise balanced design, where there are some constraints on the size of one block or the size of the largest block. For every positive integers <span id="mmlsi2" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003192&_mathId=si2.gif&_user=111111111&_pii=S0012365X15003192&_rdoc=1&_issn=0012365X&md5=53a743bae037cdbfffe815403502d9ef" title="Click to view the MathML source">n,mspan><span class="mathContainer hidden"><span class="mathCode">f" overflow="scroll">n,mspan>span>span>, where <span id="mmlsi3" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003192&_mathId=si3.gif&_user=111111111&_pii=S0012365X15003192&_rdoc=1&_issn=0012365X&md5=cad8a91a76dae68795aa28d3ace625d4" title="Click to view the MathML source">m≤nspan><span class="mathContainer hidden"><span class="mathCode">f" overflow="scroll">m≤nspan>span>span>, let <span id="mmlsi4" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003192&_mathId=si4.gif&_user=111111111&_pii=S0012365X15003192&_rdoc=1&_issn=0012365X&md5=7c31bfca984070a426b8219b0a4edfd5" title="Click to view the MathML source">S(n,m)span><span class="mathContainer hidden"><span class="mathCode">f" overflow="scroll">script">S(n,m)span>span>span> be the smallest integer <span id="mmlsi5" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003192&_mathId=si5.gif&_user=111111111&_pii=S0012365X15003192&_rdoc=1&_issn=0012365X&md5=b149d6248d1b2d517de8633e7a750843" title="Click to view the MathML source">sspan><span class="mathContainer hidden"><span class="mathCode">f" overflow="scroll">sspan>span>span> for which there exists a PBD on <span id="mmlsi6" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003192&_mathId=si6.gif&_user=111111111&_pii=S0012365X15003192&_rdoc=1&_issn=0012365X&md5=bd883150620b4bed51dcaaea70df17e0" title="Click to view the MathML source">nspan><span class="mathContainer hidden"><span class="mathCode">f" overflow="scroll">nspan>span>span> points whose largest block has size <span id="mmlsi7" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003192&_mathId=si7.gif&_user=111111111&_pii=S0012365X15003192&_rdoc=1&_issn=0012365X&md5=7f6129abdc6e00ead2dbae9725c38dd7" title="Click to view the MathML source">mspan><span class="mathContainer hidden"><span class="mathCode">f" overflow="scroll">mspan>span>span> and the sum of its block sizes is equal to <span id="mmlsi5" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003192&_mathId=si5.gif&_user=111111111&_pii=S0012365X15003192&_rdoc=1&_issn=0012365X&md5=b149d6248d1b2d517de8633e7a750843" title="Click to view the MathML source">sspan><span class="mathContainer hidden"><span class="mathCode">f" overflow="scroll">sspan>span>span>. Also, let <span id="mmlsi9" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003192&_mathId=si9.gif&_user=111111111&_pii=S0012365X15003192&_rdoc=1&_issn=0012365X&md5=01a5210af843b31194f69101b3db5310" title="Click to view the MathML source">S<sup>′sup>(n,m)span><span class="mathContainer hidden"><span class="mathCode">f" overflow="scroll">sup>script">S′sup>(n,m)span>span>span> be the smallest integer <span id="mmlsi5" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003192&_mathId=si5.gif&_user=111111111&_pii=S0012365X15003192&_rdoc=1&_issn=0012365X&md5=b149d6248d1b2d517de8633e7a750843" title="Click to view the MathML source">sspan><span class="mathContainer hidden"><span class="mathCode">f" overflow="scroll">sspan>span>span> for which there exists a PBD on <span id="mmlsi6" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003192&_mathId=si6.gif&_user=111111111&_pii=S0012365X15003192&_rdoc=1&_issn=0012365X&md5=bd883150620b4bed51dcaaea70df17e0" title="Click to view the MathML source">nspan><span class="mathContainer hidden"><span class="mathCode">f" overflow="scroll">nspan>span>span> points which has a block of size <span id="mmlsi7" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003192&_mathId=si7.gif&_user=111111111&_pii=S0012365X15003192&_rdoc=1&_issn=0012365X&md5=7f6129abdc6e00ead2dbae9725c38dd7" title="Click to view the MathML source">mspan><span class="mathContainer hidden"><span class="mathCode">f" overflow="scroll">mspan>span>span> and the sum of it block sizes is equal to <span id="mmlsi5" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003192&_mathId=si5.gif&_user=111111111&_pii=S0012365X15003192&_rdoc=1&_issn=0012365X&md5=b149d6248d1b2d517de8633e7a750843" title="Click to view the MathML source">sspan><span class="mathContainer hidden"><span class="mathCode">f" overflow="scroll">sspan>span>span>. We prove some lower bounds for <span id="mmlsi4" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003192&_mathId=si4.gif&_user=111111111&_pii=S0012365X15003192&_rdoc=1&_issn=0012365X&md5=7c31bfca984070a426b8219b0a4edfd5" title="Click to view the MathML source">S(n,m)span><span class="mathContainer hidden"><span class="mathCode">f" overflow="scroll">script">S(n,m)span>span>span> and <span id="mmlsi9" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003192&_mathId=si9.gif&_user=111111111&_pii=S0012365X15003192&_rdoc=1&_issn=0012365X&md5=01a5210af843b31194f69101b3db5310" title="Click to view the MathML source">S<sup>′sup>(n,m)span><span class="mathContainer hidden"><span class="mathCode">f" overflow="scroll">sup>script">S′sup>(n,m)span>span>span>. Moreover, we apply these bounds to determine the asymptotic behaviour of the sigma clique partition number of the graph <span id="mmlsi16" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003192&_mathId=si16.gif&_user=111111111&_pii=S0012365X15003192&_rdoc=1&_issn=0012365X&md5=d401cb72e60d47984ad1ff555adb54e5" title="Click to view the MathML source">K<sub>nsub>&minus;K<sub>msub>span><span class="mathContainer hidden"><span class="mathCode">f" overflow="scroll">sub>Knsub>&minus;sub>Kmsub>span>span>span>, the Cocktail party graphs and complement of paths and cycles.