Results on Independent Sets in Categorical Products of Graphs, the Ultimate Categorical Independence Ratio and the Ultimate Categorical Independent Domination Ratio

详细信息    查看全文

• 作者：Wing-Kai Hon (18)
  Ton Kloks (18)
  Ching-Hao Liu (18)
  Hsiang-Hsuan Liu (18)
  Sheung-Hung Poon (18)
  Yue-Li Wang (19)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8344
• 期：1
• 页码：237-248
• 全文大小：252 KB
• 参考文献：1. Albertson, M., Collins, K.: Homomorphisms of 3-chromatic graphs. Discrete Mathematics?54, 127-32 (1985) CrossRef
  2. Alon, N., Lubetzky, E.: Independent sets in tensor graph powers. Journal of Graph Theory?54, 73-7 (2007) 20194" target="_blank" title="It opens in new window">CrossRef
  3. Aurenhammer, F., Hagauer, J., Imrich, W.: Cartesian graph factorization at logarithmic cost per edge. Computational Complexity?2, 331-49 (1992) 200428" target="_blank" title="It opens in new window">CrossRef
  4. Brown, J., Nowakowski, R., Rall, D.: The ultimate categorical independence ratio of a graph. SIAM Journal on Discrete Mathematics?9, 290-00 (1996) 194276909" target="_blank" title="It opens in new window">CrossRef
  5. Chartrand, G., Kapoor, S.F., Lick, D.R., Schuster, S.: The partial complement of graphs. Periodica Mathematica Hungarica?16, 83-5 (1985) CrossRef
  6. Corneil, D., Perl, Y., Stuwart, L.: A linear recognition algorithm for cographs. SIAM Journal on Computing?14, 926-34 (1985) CrossRef
  7. Cunningham, W.: Computing the binding number of a graph. Discrete Applied Mathematics?27, 283-85 (1990) CrossRef
  8. Hahn, G., Hell, P., Poljak, S.: On the ultimate independence ratio of a graph. European Journal of Combinatorics?16, 253-61 (1995) 195-6698(95)90030-6" target="_blank" title="It opens in new window">CrossRef
  9. 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-66. Kluwer (1997)
  10. Hedetniemi, S.: Homomorphisms of graphs and automata. Technical report 03105-44-T, University of Michigan (1966)
  11. Hell, P., Ne?et?il, J.: Graphs and homomorphisms. Oxford Univ. Press (2004)
  12. Hell, P., Yu, X., Zhou, H.: Independence ratios of graph powers. Discrete Mathematics?27, 213-20 (1994) CrossRef
  13. Jha, P., Klav?ar, S.: Independence in direct-product graphs. Ars Combinatoria?50, 53-3 (1998)
  14. Kloks, T., Lee, C., Liu, J.: Stickiness, edge-thickness, and clique-thickness in graphs. Journal of Information Science and Engineering?20, 207-17 (2004)
  15. Kloks, T., Wang, Y.: Advances in graph algorithms (Manuscript 2013)
  16. Lubetzky, E.: Graph powers and related extremal problems. PhD Thesis, Tel Aviv University, Israel (2007)
  17. Moon, J., Moser, L.: On cliques in graphs. Israel Journal of Mathematics?3, 23-8 (1965) CrossRef
  18. Ravindra, G., Parthasarathy, K.: Perfect product graphs. Discrete Mathematics?20, 177-86 (1977) CrossRef
  19. Tóth, á.: Answer to a question of Alon and Lubetzky about the ultimate categorical independence ratio. Manuscript on arXiv:1112.6172v1 (2011)
  20. Tóth, á.: The ultimate categorical independence ratio of complet multipartite graphs. SIAM Journal on Discrete Mathematics?23, 1900-904 (2009) CrossRef
  21. Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM Journal on Computing?6, 505-17 (1977) 206036" target="_blank" title="It opens in new window">CrossRef
  22. Weichsel, P.: The Kronecker product of graphs. Proceedings of the American mathematical Society?13, 47-2 (1962) 1962-0133816-6" target="_blank" title="It opens in new window">CrossRef
  23. Woodall, D.: The binding number of a graph and its Anderson number. Journal of Combinatorial Theory, Series B?15, 225-55 (1973) CrossRef
  24. Zhang, H.: Independent sets in direct products of vertex-transitive graphs. Journal of Combinatorial Theory, Series B?102, 832-38 (2012) 2011.12.005" target="_blank" title="It opens in new window">CrossRef
  25. Zhu, X.: The fractional version of Hedetniemi’s conjecture is true. European Journal of Combinatorics?32, 1168-175 (2011) 2011.03.004" target="_blank" title="It opens in new window">CrossRef
  
• 作者单位：Wing-Kai Hon (18)
  Ton Kloks (18)
  Ching-Hao Liu (18)
  Hsiang-Hsuan Liu (18)
  Sheung-Hung Poon (18)
  Yue-Li Wang (19)
  
  18. Department of Computer Science, National Tsing Hua University, Taiwan
  19. Department of Information Management, National Taiwan University of Science and Technology, Taiwan
  
• ISSN：1611-3349

文摘

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?→?∞-/sub> α(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 ??-/sup>(3 n/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).