Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl

PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2012 | 32 | 2 | 299-319

Tytuł artykułu

Domination in functigraphs

Treść / Zawartość

Warianty tytułu

Języki publikacji

EN

Abstrakty

EN
Let G₁ and G₂ be disjoint copies of a graph G, and let f:V(G₁) → V(G₂) be a function. Then a functigraph C(G,f) = (V,E) has the vertex set V = V(G₁) ∪ V(G₂) and the edge set E = E(G₁) ∪ E(G₂) ∪ {uv | u ∈ V(G₁), v ∈ V(G₂),v = f(u)}. A functigraph is a generalization of a permutation graph (also known as a generalized prism) in the sense of Chartrand and Harary. In this paper, we study domination in functigraphs. Let γ(G) denote the domination number of G. It is readily seen that γ(G) ≤ γ(C(G,f)) ≤ 2 γ(G). We investigate for graphs generally, and for cycles in great detail, the functions which achieve the upper and lower bounds, as well as the realization of the intermediate values.

Wydawca

Rocznik

Tom

32

Numer

2

Strony

299-319

Opis fizyczny

Daty

wydano
2012
otrzymano
2010-07-12
poprawiono
2011-06-06
zaakceptowano
2011-06-06

Twórcy

autor
  • Department of Mathematics, University of Wisconsin Oshkosh, Oshkosh, WI 54901, USA
autor
  • Department of Applied Mathematics, Naval Postgraduate School, Monterey, CA 93943, USA
autor
  • Department of General Academics, Texas A&M University at Galveston, Galveston, TX 77553, USA
  • Department of Mathematics and Applied Mathematics, Virginia Commonwealth University, Richmond, VA 23284, USA
autor
  • Department of General Academics, Texas A&M University at Galveston, Galveston, TX 77553, USA

Bibliografia

  • [1] S. Benecke, Domination of generalized Cartesian products, Ph.D. Dissertation (University of Victoria, 2009).
  • [2] S. Benecke and C.M. Mynhardt, Domination of generalized Cartesian products, Discrete Math. 310 (2010) 1392-1397, doi: 10.1016/j.disc.2009.12.007.
  • [3] C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam,1973).
  • [4] C. Berge, Theory of Graphs and its Applications (Methuen, London, 1962).
  • [5] A.P. Burger and C.M. Mynhardt, Regular graphs are not universal fixers, Discrete Math. 310 (2010) 364-368, doi: 10.1016/j.disc.2008.09.016.
  • [6] A.P. Burger, C.M. Mynhardt and W.D. Weakley, On the domination number of prisms of graphs, Discuss. Math. Graph Theory 24 (2004) 303-318, doi: 10.7151/dmgt.1233.
  • [7] G. Chartrand and F. Harary, Planar permutation graphs, Ann. Inst. H. Poincare (Sect. B) 3 (1967) 433-438.
  • [8] G. Chartrand and P. Zhang, Introduction to Graph Theory (McGraw-Hill, Kalamazoo, MI, 2004).
  • [9] A. Chen, D. Ferrero, R. Gera and E. Yi, Functigraphs: An Extension of Permutation Graphs, Math. Bohem. 136 (2011) 27-37.
  • [10] E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977) 247-261, doi: 10.1002/net.3230070305.
  • [11] W. Dörfler, On mapping graphs and permutation graphs, Math. Slovaca 28 (1978) 277-288.
  • [12] B.L. Hartnell and D.F. Rall, On dominating the cartesian product of a graph and K₂, Discuss. Math. Graph Theory 24 (2004) 389-402, doi: 10.7151/dmgt.1238.
  • [13] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998).
  • [14] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
  • [15] S.T. Hedetniemi, On classes of graphs defined by special cutsets of lines, Many Facets of Graph Theory, Lect. Notes Math. 110 (1969) 171-189, doi: 10.1007/BFb0060115.
  • [16] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ., 38, Providence, 1962).

Typ dokumentu

Bibliografia

Identyfikatory

Identyfikator YADDA

bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1600
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.