본문 바로가기
KERD
논문KCI 등재

Bounding the Search Number of Graph Products

Margaret-Ellen Messinger|Grace Power|Nancy Ellen Clarke
경북대학교 자연과학대학 수학과|2019.03|Kyungpook Mathematical Journal|제59권 제1호|pp. 175-190|DOI 10.5666/KMJ.2019.59.1.175

2

조회

0

다운로드

0

인용

0

참고문헌

키워드

graph searchingsweepingpathwidth
주제분류수학

초록

In this paper, we provide results for the search number of the Cartesian product of graphs. We consider graphs on opposing ends of the spectrum: paths and cliques. Our main result determines the pathwidth of the product of cliques and provides a lower bound for the search number of the product of cliques. A consequence of this result is a bound for the search number of the product of arbitrary graphs G and H based on their respective clique numbers.

Abstract

In this paper, we provide results for the search number of the Cartesian product of graphs. We consider graphs on opposing ends of the spectrum: paths and cliques. Our main result determines the pathwidth of the product of cliques and provides a lower bound for the search number of the product of cliques. A consequence of this result is a bound for the search number of the product of arbitrary graphs G and H based on their respective clique numbers.

참고문헌 (21)

  1. B. Alspach, "Searching and sweeping graphs : a brief survey", Matematiche(Catania), 59, pp.5~37 (2004)
  2. H. L. Bodlaender, "A partial k-arboretum of graphs with bounded treewidth", Theoret. Comput. Sci, 209, pp.1~45 (1998)
  3. H. L. Bodlaender, "Dynamic programming algorithms on graphs with bounded treewidth", Proc. 15th Intemat. Coil. on Automata, Languages and Programming, Lecture Notes in Computer Science, 317, pp.105~119 (1988), Springer
  4. H. L. Bodlaender, "The pathwidth and treewidth of cographs", SIAM J. Discrete Math, 6, pp.181~188 (1993)
  5. D. Dyer, "Sweeping graphs and digraphs", Ph.D, pp.2004
  6. J. A. Ellis, "The vertex separation and search number of a graph", Inform. Comput, 113, pp.50~79 (1994)
  7. J. Ellis, "Lower bounds on the pathwidth of some grid-like graphs", Discrete Appl. Math, 156, pp.545~555 (2008)
  8. M. Fellows, "On search, decision and the efficiency of polynomial time algorithms", J. Comput. System Sci, 49, pp.769~779 (1994)
  9. M. Frankling, "Eavesdropping games : a graph theoretic approach to privacy in distributed systems", J. ACM, 47, pp.225~243 (2000)
  10. P. Heggernes, "Edge search number of cographs in linear time", Front. Algorithmics, Lecture Notes in Computer Science, 5598, pp.16~26 (2009)
  11. N. G. Kinnersley, "The vertex separation number of a graph equals its path-width", Inform. Process. Lett, 42, pp.345~350 (1992)
  12. L. M. Kirousis, "Searching and pebbling", Theoret. Comput. Sci, 47(2), pp.205~218 (1986)
  13. B. Lucena, "Achievable sets, brambles, and sparse treewidth obstructions", Disc. Appl. Math, 155, pp.1055~1065 (2007)
  14. N. Megiddo, "The complexity of searching a graph", J. Assoc. Ccomp. Mach, 35, pp.18~44 (1988)
  15. M. E. Messinger, "Cleaning a network with brushes", Theoret. Comput. Sci, 399, pp.191~205 (2008)
  16. N. Robertson., "Graph minors. I. Excluding a forest", J. Combin. Theory Ser. B, 35, pp.39~61 (1983)
  17. N. Robertson, "Graph minors. II. Algorithmic aspects of tree-width", J. Algorithms, 7, pp.309~322 (1986)
  18. P. Scheffler, "Die Baumweite von Graphen als ein Maβ fur die Kompliziertheit algorithmischer Probleme", Ph.D., pp.1989
  19. P. D. Seymour, "Graph searching and a mini-max theorem for treewidth", J. Combin. Theory Ser. B, 58, pp.22~33 (1993)
  20. R. Tosic, "Search number of the cartesian product of graphs", Univ. Novom Sabu Zb. Rad. Prirod.-Mat Fak. Ser. Mat, 17, pp.239~243 (1987)
  21. B. Yang, "Sweeping graphs with large clique number", Discrete Math, 309, pp.5770~5780 (2009)

관련 논문AI추천

Strong Roman Domination in Grid Graphs손무영, Xue-gang Chen경북대학교 자연과학대학 수학과 · Kyungpook Mathematical Journal2019 · 제59권 제3호Double Domination in the Cartesian and Tensor Products of GraphsArnel Marino Cuivillas, Sergio R. Canoy, Jr.경북대학교 자연과학대학 수학과 · Kyungpook Mathematical Journal2015 · 제55권 제2호On the Metric Dimension of Corona Product of a Graph with K1Mohsen Jannesari경북대학교 자연과학대학 수학과 · Kyungpook Mathematical Journal2023 · 제63권 제1호ON BOUNDS AND EXACT VALUES OF k-EFFICIENT DOMINATION NUMBER OF A GRAPHCHANDRU HEGDE, Karthik K, Kavitha Nagandla장전수학회 · Proceedings of the Jangjeon Mathematical Society(장전수학회 논문집)2024 · 제27권 제4호Locating-Hop Domination in GraphsGemma P. Salasalan, Sergio R. Canoy, Jr.경북대학교 자연과학대학 수학과 · Kyungpook Mathematical Journal2022 · 제62권 제1호Distance Pattern Distinguishing Sets in GraphsK.A. Germina, R. Ananthakumar장전수학회 · Advanced Studies in Contemporary Mathematics2011 · 제21권 제1호

이 간행물의 다른 논문 (14건)

Study of Generalized Derivations in Rings with InvolutionAdnan Abbasi, Muzibur Rahman Mozumder, Nadeem Ahmad Darpp. 1-11On a Symbolic Method for Fully Inhomogeneous Boundary Value ProblemsSrinivasarao Thotapp. 13-22New Approach to Pell and Pell-Lucas SequencesTulay Yagmurpp. 23-34On Regular Γ-semihyperrings and Idempotent Γ-semihyperringsJitendra Jaysing Patil, Kishor Fakira Pawarpp. 35-45A Note on Spliced Sequences and A-density of Points with respect to a Non-negative MatrixSayan Sengupta, Kumardipta Bosepp. 47-63
원문 보기