scientific article; zbMATH DE number 4103106

From MaRDI portal
Publication:3828030





[For the entire collection see Zbl 0665.00002.] Let G be a graph with vertices \(v_ 1,v_ 2,...,v_ p\). Let S be a vertex set in G. Then the coordinate vector generated by S is the vector whose \(i^{th}\) entry is the number of neighbors of \(v_ i\) in S. The notion of coordinates with respect to independent sets was introduced by \textit{S. Fajtlowicz} [Proc. 8th southeast. Conf. on Combinatorics, graph theory, and computing; Baton Rouge 1977, 273-277 (1977; Zbl 0427.05045)], and was used by him [Proc. 9th southeast. Conf. on Combinatorics, graph theory, and computing, Boca Raton 1978, 269-274 (1978; Zbl 0434.05044) and Combinatorica 4, 35-38 (1984; Zbl 0576.05025)] and \textit{G. Hopkins} and \textit{W. Staton} [Can. Math. Bull. 25, 179-186 (1982; Zbl 0436.05033)] in deriving lower bounds on the size of maximum independent sets in graphs. Recently, the computer program Graffiti, developed by Fajtlowicz at the University of Houston, has made a number of conjectures in involving coordinates with respect to certain special vertex sets. Our purpose in this article is to present solutions to several such conjectures and to discuss some others which we find particularly interesting.











This page was built for publication:

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