Abstract | ||
---|---|---|
Let G(1) and G(2) be disjoint copies of a graph G, and let f :V(G(1)) -> V(G(2)) be a function. Then a functigraph C(G, f) = (V, E) has the vertex set V = V(C1) boolean OR V(G(2)) and the edge set E = E(G(1)) boolean OR E(G(2)) boolean OR {uv vertical bar is an element of V (G(1)), v is an element of V(G(2)), 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 gamma(G) denote the domination number of G. It is readily seen that gamma(G) <= gamma(C(G, f)) <= 2 gamma(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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.7151/dmgt.1600 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | Field | DocType |
domination,permutation graphs,generalized prisms,functigraphs | Permutation graph,Discrete mathematics,Graph,Combinatorics,Disjoint sets,Vertex (geometry),Bound graph,Upper and lower bounds,Domination analysis,Mathematics | Journal |
Volume | Issue | ISSN |
32 | 2 | 1234-3099 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Linda Eroh | 1 | 110 | 17.85 |
Ralucca Gera | 2 | 37 | 14.62 |
Cong X. Kang | 3 | 7 | 3.27 |
Craig E. Larson | 4 | 15 | 4.55 |
Eunjeong Yi | 5 | 3 | 4.49 |