Abstract
We first present polynomial algorithms to compute maximum independent sets in the categorical products of two cographs or two splitgraphs, respectively. Then we prove that computing the independent set of the categorical product of a planar graph of maximal degree three and K 4 is NP-complete. The ultimate categorical independence ratio of a graph G is defined as lim k → ∞ α(G k)/n k. The ultimate categorical independence ratio can be computed in polynomial time for cographs, permutation graphs, interval graphs, graphs of bounded treewidth and splitgraphs. Also, we present an O ∗ (3n/3) exact, exponential algorithm for the ultimate categorical independence ratio of general graphs. We further present a PTAS for the ultimate categorical independence ratio of planar graphs. Lastly, we show that the ultimate categorical independent domination ratio for complete multipartite graphs is zero, except when the graph is complete bipartite with color classes of equal size (in which case it is 1/2).
Supported in part by grants 100-2628-E-007-020-MY3 and 101-2218-E-007-001 of the National Science Council (NSC), Taiwan, R.O.C.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Albertson, M., Collins, K.: Homomorphisms of 3-chromatic graphs. Discrete Mathematics 54, 127–132 (1985)
Alon, N., Lubetzky, E.: Independent sets in tensor graph powers. Journal of Graph Theory 54, 73–87 (2007)
Aurenhammer, F., Hagauer, J., Imrich, W.: Cartesian graph factorization at logarithmic cost per edge. Computational Complexity 2, 331–349 (1992)
Brown, J., Nowakowski, R., Rall, D.: The ultimate categorical independence ratio of a graph. SIAM Journal on Discrete Mathematics 9, 290–300 (1996)
Chartrand, G., Kapoor, S.F., Lick, D.R., Schuster, S.: The partial complement of graphs. Periodica Mathematica Hungarica 16, 83–95 (1985)
Corneil, D., Perl, Y., Stuwart, L.: A linear recognition algorithm for cographs. SIAM Journal on Computing 14, 926–934 (1985)
Cunningham, W.: Computing the binding number of a graph. Discrete Applied Mathematics 27, 283–285 (1990)
Hahn, G., Hell, P., Poljak, S.: On the ultimate independence ratio of a graph. European Journal of Combinatorics 16, 253–261 (1995)
Hahn, G., Tardif, C.: Graph homomorphisms: structure and symmetry. In: Graph Symmetry – Algebraic Methods and Applications. NATO ASI Series C: Mathematical and Physical Sciences, vol. 497, pp. 107–166. Kluwer (1997)
Hedetniemi, S.: Homomorphisms of graphs and automata. Technical report 03105-44-T, University of Michigan (1966)
Hell, P., Nešetřil, J.: Graphs and homomorphisms. Oxford Univ. Press (2004)
Hell, P., Yu, X., Zhou, H.: Independence ratios of graph powers. Discrete Mathematics 27, 213–220 (1994)
Jha, P., Klavžar, S.: Independence in direct-product graphs. Ars Combinatoria 50, 53–63 (1998)
Kloks, T., Lee, C., Liu, J.: Stickiness, edge-thickness, and clique-thickness in graphs. Journal of Information Science and Engineering 20, 207–217 (2004)
Kloks, T., Wang, Y.: Advances in graph algorithms (Manuscript 2013)
Lubetzky, E.: Graph powers and related extremal problems. PhD Thesis, Tel Aviv University, Israel (2007)
Moon, J., Moser, L.: On cliques in graphs. Israel Journal of Mathematics 3, 23–28 (1965)
Ravindra, G., Parthasarathy, K.: Perfect product graphs. Discrete Mathematics 20, 177–186 (1977)
Tóth, Á.: Answer to a question of Alon and Lubetzky about the ultimate categorical independence ratio. Manuscript on arXiv:1112.6172v1 (2011)
Tóth, Á.: The ultimate categorical independence ratio of complet multipartite graphs. SIAM Journal on Discrete Mathematics 23, 1900–1904 (2009)
Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM Journal on Computing 6, 505–517 (1977)
Weichsel, P.: The Kronecker product of graphs. Proceedings of the American mathematical Society 13, 47–52 (1962)
Woodall, D.: The binding number of a graph and its Anderson number. Journal of Combinatorial Theory, Series B 15, 225–255 (1973)
Zhang, H.: Independent sets in direct products of vertex-transitive graphs. Journal of Combinatorial Theory, Series B 102, 832–838 (2012)
Zhu, X.: The fractional version of Hedetniemi’s conjecture is true. European Journal of Combinatorics 32, 1168–1175 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Hon, WK., Kloks, T., Liu, CH., Liu, HH., Poon, SH., Wang, YL. (2014). Results on Independent Sets in Categorical Products of Graphs, the Ultimate Categorical Independence Ratio and the Ultimate Categorical Independent Domination Ratio. In: Pal, S.P., Sadakane, K. (eds) Algorithms and Computation. WALCOM 2014. Lecture Notes in Computer Science, vol 8344. Springer, Cham. https://doi.org/10.1007/978-3-319-04657-0_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-04657-0_23
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04656-3
Online ISBN: 978-3-319-04657-0
eBook Packages: Computer ScienceComputer Science (R0)