Please use this identifier to cite or link to this item: https://idr.l3.nitk.ac.in/jspui/handle/123456789/12369
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSowmya, Kamath S.-
dc.contributor.authorBhat, R.S.-
dc.date.accessioned2020-03-31T08:39:05Z-
dc.date.available2020-03-31T08:39:05Z-
dc.date.issued2007-
dc.identifier.citationDiscrete Mathematics, 2007, Vol.307, 44113, pp.1136-1145en_US
dc.identifier.urihttps://idr.nitk.ac.in/jspui/handle/123456789/12369-
dc.description.abstractA vertex v in a graph G = (V, E) is strong (weak) if deg (v) ? deg (u)(deg (v) ? deg (u)) for every u adjacent to v in G. A set S ? V is said to be strong (weak) if every vertex in S is a strong (weak) vertex in G. A strong (weak) set which is independent is called a strong independent set [SIS] (weak independent set [WIS]). The strong (weak) independence numbers ? = s ? (G) (w ? = w ? (G)) is the maximum cardinality of an SIS (WIS). For an edge x = uv, v strongly covers the edge x if deg (v) ? deg (u) in G. Then u weakly covers x. A set S ? V is a strong vertex cover [SVC] (weak vertex cover [WVC]) if every edge in G is strongly (weakly) covered by some vertex in S. The strong (weak) vertex covering numbers ? = s ? (G)(w ? = w ? (G)) is the minimum cardinality of an SVC (WVC). In this paper, we investigate some relationships among these four new parameters. For any graph G without isolated vertices, we show that the following inequality chains hold: s ? ? ? ? s ? ? w ? and s ? ? w ? ? ? ? w ?. Analogous to Gallai's theorem, we prove s ? + w ? = p and w ? + s ? = p. Further, we show that s ? ? p - ? and w ? ? p - ? and find a necessary and sufficient condition to attain the upper bound, characterizing the graphs which attain these bounds. Several Nordhaus-Gaddum-type results and a Vizing-type result are also established. 2006.en_US
dc.titleOn strong (weak) independent sets and vertex coverings of a graphen_US
dc.typeArticleen_US
Appears in Collections:1. Journal Articles

Files in This Item:
File Description SizeFormat 
12369.pdf168.06 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.