×

Generalised maximal independence parameters for paths and cycles. (English) Zbl 0757.05097

A set \(B\) of vertices of a graph \(G=(V,E)\) is a \(k\)-maximal independent set \((kMIS)\) if \(B\) is independent but for all \(\ell\)-subsets \(X\) of \(B\), \(\ell\leq k-1\), and all \((\ell+1)\)-subsets \(Y\) of \(V-B\), \((B-X)\cup Y\) is dependent. Let \(\beta_ k(G)\) denote the smallest cardinality of a \(kMIS\) of \(G\). The main results characterize the \(kMIS\) of \(n\)-cycle \(C_ n\) and that of \(n\)-path \(P_ n\). Any maximal independent set \(B\) of \(C_ n\) divides \(C_ n\) into segments of 3 or 4 vertices. Then it is proved that the maximal independent set \(B\) is a \(kMIS\) of \(C_ n\) if and only if each pair of distinct segments of 4 vertices is separated by at least \((k-1)\) segments of 3 vertices. Similar result is obtained for a maximal independent set \(B\) being a \(kMIS\) of \(P_ n\).
Let \(n=q(2k+1)+r\) where \(0\leq r<2k+1\) for any \(k\). Then \[ \beta_ k(C_ n)=\begin{cases} \left\lfloor{n\over 2}\right\rfloor\quad & \text{if } n<4k+2 \\ kq+\left\lceil{n\over 2}\right\rceil & \text{if } n\geq 4k+2 \end{cases} \] and \[ \beta_ k(P_ n)=\beta_ k(C_{n+2k+1})-k. \] Some interesting possible topics are given for further research.
Reviewer: H.Li (Orsay)

MSC:

05C99 Graph theory
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bowkett KM, Smith DA (1970) Field Ion Microscopy. North Holland, New York, NY, pp. 104–141–145–149
[2] Miller MK, Horton JA (1987) J de Phys 48-C6:379
[3] Jayaram R, Miller MK (1995) Scripta Metall 33:19
[4] Chang L, Barnard SJ, Smith GDW (1992) In: Krauss G, Repas PE (eds) Fundamentals of aging and tempering in Bainitic and Martensitic steel products, The Iron and Steel Society, Warrendale, PA, p 19
[5] Miller MK, Cerezo A, Hetherington MG, Smith GDW (1996) Atom probe field ion microscopy. Oxford University Press, Oxford, UK
[6] Miller MK (2004) TMS Lett 1:19
[7] Miller MK (2006) Microsc Res Tech 69:359
[8] Smith DA, Birdseye PJ, Goringe MJ (1973) Phil Mag 27:1175
[9] Miller MK (2000) Atom probe tomography. Kluwer Academic/Plenum Press, New York, NY · doi:10.1007/978-1-4615-4281-0
[10] Blavette D, Cadel E, Fraczkiewicz A, Menand A (1999) Science 286:2317
[11] Wilde J, Cerezo A, Smith GDW (2000) Scripta Mater 43:39
[12] Miller MK, Russell KF, Kocik J, Keilova E (2000) J Nucl Mater 282:83
[13] Miller MK, Pareige P (2000) In: Lucas GE, Snead LL, Kirk MA, Elliman RG (eds) Material Research Society Symposium R: Microstructural processes in irradiated materials, November 27–29, 2000, vol. 650, Material Research Society, Warrendale, PA, p R6.1.1
[14] Miller MK, Russell KF, Kocik J, Keilova E (2001) Micron 32:749
[15] Miller MK, Kenik EA, Russell KF, Heatherly L, Hoelzer DT, Maziasz PJ (2003) Mater Sci Eng A A353:140 · doi:10.1016/S0921-5093(02)00680-9
[16] Pareige P, Radiquet B, Suvorov A, Kozodaev M, Krasikov E, Zabusov O, Massoud JP (2004) Surf Interface Anal 36:581
[17] Miller MK, Russell KF, Thompson GB (2005) Ultramicroscopy 102:287
[18] Sokolov MA, Nanstad RK (2006) Proceedings of ASME Pressure Vessels and Piping Division Conference, July 23–27, 2006, Vancouver, BC, Canada, in press
[19] Pereloma EV, Miller MK (2005) Microsc Microanal 11(suppl. 2):876
[20] Hyde JM (1993) Computer modeling and analysis of microscale phase transformations, D. Phil Thesis, Oxford University, Oxford, UK
[21] Hyde JM, English CA (2001) In: Lucas GE, Snead L, Kirk MA Jr, Elliman RG (eds) Proceedings of MRS 2000 Fall Meeting, Symposium R: Microstructural processes in irradiated materials, Boston, MA, November 27–30, 2000, vol. 650, Materials Research Society, Pittsburgh, PA, p R6.6.1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.