Premium
A generalized measure of independence and the strong product of graphs
Author(s) -
Barnes B. H.,
Mackey K. E.
Publication year - 1978
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230080206
Subject(s) - mathematics , graph , independence (probability theory) , product (mathematics) , independence number , measure (data warehouse) , independent set , combinatorics , maximal independent set , discrete mathematics , product measure , direct product , line graph , computer science , pathwidth , statistics , data mining , geometry
This work extends the results of M. Rosenfeld [6] on universal graphs with respect to the strong graph product. By using a generalized measure of independence, one can get improved bounds on the growth of the maximum independent set size under this graph product. Furthermore, a necessary and sufficient condition is derived for when the maximum independent set of the product graph is strictly greater than the product of the maximum independent sets.