The forcing connected detour number of a graph
DOI:
https://doi.org/10.4067/S0716-09172014000200002Keywords:
Detour, connected detour set, connected detour basis, connected detour number, forcing connected detour number, desvío, conjunto de desvío conectado, base conectada de desvío, número de desvío conectado, número de desvío conectado forzado.Abstract
For two vertices u and v in a graph G = (V, E), the detour distance D(u, v) is the length of a longest u—v path in G.A u—v path of length D(u, v) is called a u—v detour. A set ⊆ V is called a detour set of G if every vertex in G lies on a detour joining a pair of vertices of S.The detour number dn(G) of G is the minimum order of its detour sets and any detour set of order dn(G) is a detour basis of G.A set ⊆ V is called a connected detour set of G if S is detour set of G and the subgraph G[S] induced by S is connected. The connected detour number cdn(G) of G is the minimum order of its connected detour sets and any connected detour set of order cdn(G) is called a connected detour basis of G.A subset T of a connected detour basis S is called a forcing subset for S if S is theuniquecon-nected detour basis containing T. A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing connected detour number of S, denoted by fcdn(S), is the cardinality of a minimum forcing subset for S. The forcing connected detour number of G, denoted by fcdn(G),is fcdn(G) = min{fcdn(S)},where the minimum is taken over all connected detour bases S in G. The forcing connected detour numbers ofcertain standard graphs are obtained. It is shown that for each pair a, b of integers with 0 ≤ a < b and b ≥ 3, there is a connected graph G with fcdn(G) = a and cdn(G) = b.References
[1] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, Reading MA, (1990).
[2] G. Chartrand, H. Escuadro and P. Zhang, Detour distance in graphs, J. Combin. Math. Combin. Comput., 53, pp. 75-94, (2005).
[3] G. Chartrand, L. Johns, and P. Zhang, Detour Number of a Graph, Util. Math. 64, pp. 97—113, (2003).
[4] G. Chartrand and P. Zhang, Distance in Graphs—Taking the Long View, AKCE J. Graphs.1. No.1, pp. 1—13, (2004).
[5] G. Chartrand and P. Zang, Introduction to Graph Theory, Tata McGraw-Hill, (2006).
[6] A. P. Santhakumaran and S. Athisayanathan, The connected detour number of a graph, J. Combin. Math. Combin. Comput., 69, pp. 205—218, (2009).
[2] G. Chartrand, H. Escuadro and P. Zhang, Detour distance in graphs, J. Combin. Math. Combin. Comput., 53, pp. 75-94, (2005).
[3] G. Chartrand, L. Johns, and P. Zhang, Detour Number of a Graph, Util. Math. 64, pp. 97—113, (2003).
[4] G. Chartrand and P. Zhang, Distance in Graphs—Taking the Long View, AKCE J. Graphs.1. No.1, pp. 1—13, (2004).
[5] G. Chartrand and P. Zang, Introduction to Graph Theory, Tata McGraw-Hill, (2006).
[6] A. P. Santhakumaran and S. Athisayanathan, The connected detour number of a graph, J. Combin. Math. Combin. Comput., 69, pp. 205—218, (2009).
Published
2017-03-23
How to Cite
[1]
A. P. Santhakumaran and S. Athisayanathan, “The forcing connected detour number of a graph”, Proyecciones (Antofagasta, On line), vol. 33, no. 2, pp. 147-155, Mar. 2017.
Issue
Section
Artículos
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.