Dr. David Tankus, Department of Mathematics and Computer Science
Ariel University Center of Samaria
Tuesday, November 22, 2011
15.45 – 16.45
Room 426, Building 8
Throughout this talk G = (V, E) is a simple graph with vertex set V = V (G) and edge set E = E(G).
A path is a sequence of consecutive edges in a graph. The length of a path is the number of its edges. The distance between two vertices, v and w, denoted by d(v;w), is the length of the shortest path between v and w. A path is called maximal if it is not a subpath of another path. The path spectrum of a graph is the set of lengths of all maximal paths in the graph (Jacobson et al., 1995). A set of positive integers is spectral (tree spectral) if it is the path spectrum of a connected graph (tree). This subject has aroused considerable interest (Chen et al., 2008), (Fuller et al.,2001), (Tarsi, 1996). In 2010 Chen, Faudree, and Soltes proved the following.
Theorem 1. If s ³ 2 is even, then at least 25% of all subsets of the set {2, 3,…, s} are tree spectral.
Our main finding reads as follows.
Theorem 2. Let p ³ 7. Then:
(i) At least 34:57% of all subsets of the set {2, 3,…, 2p} are tree spectral.
(ii) At least 27:44% of all subsets of the set {2, 3,…, 2p-} are tree spectral.
Several results of this talk were presented at EuroComb 2011, Budapest.
Light refreshments will be served at 15:30.
Anyone who is interested in giving a talk in the seminar, please contact us.
