?. {2, sfc(G) = 0. ii) By the equivalence between i) and iv) in Theorem 29, for the graph G with at least 4 vertices, it holds H(G) ? 2 if and only if G is not Hamiltonian-connected, which then amounts to saying that src(G) = sfc(G) = 0. iii) On account of H(G) ? 3, Theorem 29 i) ? iv) shows that G is spanning 1-rail-connected while Theorem 30 implies that G is spanning q-rail-connected for all q , H(G)}. Finally, the equivalence between a) and g) in Theorem 22 tells us that G cannot be spanning (H(G) + 1)-rail-connected. This completes the proof of src(G) = H(G) It follows from Theorem 29 i) ? ii) that sfc(G) ? H(G) ? 1. On the other hand, Theorem 29 iii) ? i) claims that sfc(G) ? H(G) ? 1. Accordingly, we get to H(G) = sfc(G) + 1. Proof of Lemma 38: This follows from the equivalence of c) and g) in Theorem 22 Theorem 11) asserted that every connected rigid interval graph has a so-called consecutive ordering of its vertex set, which must correspond to a Hamiltonian path. Proof of Theorem 40: Recall that every connected unit interval graph is a rigid interval graph Therefore, Lemma 39 tells us that unit interval graphs form a maroon class of interval graphs. The result is now a simple consequence of Lemma 38 Theorem 10) showed that ?(G) = 2 t(G) holds for every connected noncomplete K 1,3 -free graph G while Roberts (94) told us that every unit interval graph is K 1,3 -free. Combining these with Eq, Panda and Das Theorems 33 and 40 then conclude the proof. Note that we can avoid using Matthews and Sumner Theorem 10) by directly proving 2 t(G) = min CC ?E(T ) |C ? C | where T is a clique path of the connected noncomplete unit interval graph G. Proof of Theorem 42: Let G be a Hamiltonian) and CASE 1. H(G) = H G (?) > 0. Let S = {? j : ? j ? N G (? f G (?) ), j > f G (?)}. From Theorem 44 and Eq. (55) we derive H(G ? S ) = H(G) ? |S | = 0

H. Sc, This proves that S ? S is a scattering set of G

M. Albert, R. Aldred, and D. Holton, On 3 * -connected graphs, Australasian Journal of Combinatorics, vol.24, pp.193-208, 2001.

S. Arikati and C. Pandu-rangan, Linear algorithm for optimal path cover problem on interval graphs, Information Processing Letters, vol.35, issue.3, pp.149-153, 1990.
DOI : 10.1016/0020-0190(90)90064-5

K. Asdre and S. Nikolopoulos, The 1-Fixed-Endpoint Path Cover Problem is??Polynomial on Interval Graphs, Algorithmica, vol.18, issue.3, pp.679-710, 2010.
DOI : 10.1007/s00453-009-9292-5

M. Baker and S. Norine, Riemann-Roch and Abel-Jacobi theory on a finite graph Advances in Mathematics, pp.766-788, 2007.

J. Barnett, Early Writings on Graph Theory: Hamiltonian Circuits and The Icosian Game, Resources for Teaching Discrete Mathematics: Classroom Projects, History Modules and Articles, pp.217-223, 2009.
DOI : 10.5948/UPO9780883859742.028

D. Bauer, H. Broersma, J. Van-den-heuvel, N. Kahl, and E. Schmeichel, Toughness and Vertex Degrees, Journal of Graph Theory, vol.17, issue.2, pp.209-219, 2013.
DOI : 10.1002/jgt.21639
URL : http://arxiv.org/abs/0912.2919

A. A. Bertossi, Finding Hamiltonian circuits in proper interval graphs, Information Processing Letters, vol.17, issue.2, pp.97-101, 1983.
DOI : 10.1016/0020-0190(83)90078-9

J. Bondy and U. Murty, Graph Theory, 2008.
DOI : 10.1007/978-1-84628-970-5

H. Broersma, Z. Ryjá?ek, and P. Vrána, How many conjectures can you stand? A survey. Graphs and Combinatorics, pp.57-75

H. Broersma, J. Fiala, P. Golovach, T. Kaiser, D. Paulusma et al., Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs, Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science, pp.127-138978, 2013.
DOI : 10.1007/978-3-642-45043-3_12

F. Bullock, P. Dankelmann, M. Frick, M. A. Henning, O. R. Oellermann et al., Hamiltonicity of k-traceable graphs, Electronic Journal of Combinatorics, vol.18, 2011.

J. Chang, C. Ho, and M. Ko, Powers of asteroidal triple-free graphs with applications, Ars Combinatoria, vol.67, pp.161-173, 2003.

G. Chartrand, S. Kapoor, and D. R. Lick, n-Hamiltonian graphs, Journal of Combinatorial Theory, vol.9, issue.3, pp.308-312, 1970.
DOI : 10.1016/S0021-9800(70)80069-2

C. Chen and C. Chang, Connected proper interval graphs and the guard problem in spiral polygons, Combinatorics and Computer Science Lecture Notes in Computer Science, vol.1120, pp.39-47, 1996.
DOI : 10.1007/3-540-61576-8_71

C. Chen and N. Quimpo, On strongly hamiltonian abelian group graphs, Combinatorial Mathematics VIII, Proceedings of the Eighth Australian Conference, pp.23-34, 1980.
DOI : 10.1007/978-1-349-03521-2

C. Chen, C. Chang, and G. J. Chang, Proper interval graphs and the guard problem, Discrete Mathematics, vol.170, issue.1-3, pp.223-230, 1997.
DOI : 10.1016/S0012-365X(96)00307-X

G. Chen, R. J. Gould, and F. Pfender, New conditions for k-ordered Hamiltonian graphs, Ars Combinatoria, vol.70, 2004.

G. Chen, R. J. Faudree, R. J. Gould, and M. S. Jacobson, Cycle Extendability of Hamiltonian Interval Graphs, SIAM Journal on Discrete Mathematics, vol.20, issue.3, pp.682-689, 2006.
DOI : 10.1137/S0895480104441450

X. Chen, M. Szegedy, and L. Wang, Optimally Balanced Forward Degree Sequence, Computing and Combinatorics, pp.680-689, 2005.
DOI : 10.1007/11533719_69

Y. Chen, Z. Chen, H. Lai, P. Li, and E. Wei, On Spanning Disjoint Paths in Line Graphs, Graphs and Combinatorics, vol.22, issue.51, pp.1721-1731, 2013.
DOI : 10.1007/s00373-012-1237-0

M. Chrobak and D. Eppstein, Planar orientations with low out-degree and compaction of adjacency matrices, Theoretical Computer Science, vol.86, issue.2, pp.243-266, 1991.
DOI : 10.1016/0304-3975(91)90020-3

V. Chvátal and P. Erd?-os, A note on Hamiltonian circuits, Discrete Mathematics, vol.2, issue.2, pp.111-113
DOI : 10.1016/0012-365X(72)90079-9

D. G. Corneil, E. K?-ohler, S. Olariu, and L. Stewart, Linear Orderings of Subfamilies of AT???Free Graphs, SIAM Journal on Discrete Mathematics, vol.20, issue.1, pp.105-118, 2006.
DOI : 10.1137/S0895480104445307

D. G. Corneil, B. Dalton, and M. Habib, LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs, SIAM Journal on Computing, vol.42, issue.3, pp.792-807, 11083856.
DOI : 10.1137/11083856X
URL : https://hal.archives-ouvertes.fr/hal-00936300

H. Coxeter, My Graph, Proceedings of the London Mathematical Society, Third Series, pp.117-136, 1983.
DOI : 10.1112/plms/s3-46.1.117

P. Damaschke, Paths in interval graphs and circular arc graphs, Discrete Mathematics, vol.112, issue.1-3, pp.49-64, 1993.
DOI : 10.1016/0012-365X(93)90223-G

P. Damaschke, J. S. Deogun, D. Kratsch, and G. Steiner, Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm. Order, pp.383-391, 1991.

A. M. Dean, C. J. Knickerbocker, P. F. Lock, and M. Sheard, A survey of graphs Hamiltonian-connected from a vertex, Graph Theory, Combinatorics, and Applications Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs held at Western Michigan University, pp.297-313, 1988.

J. S. Deogun, D. Kratsch, and G. Steiner, 1-Tough cocomparability graphs are hamiltonian, Discrete Mathematics, vol.170, issue.1-3, pp.99-106, 1997.
DOI : 10.1016/0012-365X(95)00359-5

G. Dirac, On rigid circuit graphs, Abhandlungen aus dem Mathematischen Seminar der Universit??t Hamburg, vol.13, issue.1-2, pp.71-76, 1961.
DOI : 10.1007/BF02992776

P. Erd?-os and A. Hajnal, On chromatic number of graphs and set-systems, Acta Mathematica Academiae Scientiarum Hungaricae, vol.24, issue.66, pp.61-99, 1966.
DOI : 10.1007/BF02020444

M. Farber, Characterizations of strongly chordal graphs, Discrete Mathematics, vol.43, issue.2-3, pp.173-189, 1983.
DOI : 10.1016/0012-365X(83)90154-1

D. Franzblau and A. Raychaudhuri, Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow, The ANZIAM Journal, vol.9, issue.02, pp.193-204, 2002.
DOI : 10.1016/0020-0190(76)90080-6

T. Gaudin, J. Herz, and P. Rossi, Solution du probl'e me no. 29. Revue Française d'Informatique et de, Recherche Opérationnelle, vol.8, pp.214-218, 1964.

V. Giakoumakis, F. Roussel, and H. Thuillier, Scattering number and modular decomposition, Discrete Mathematics, vol.165, issue.166, pp.165-166321, 1997.
DOI : 10.1016/S0012-365X(96)00180-X

V. Giakoumakis, F. Roussel, and H. Thuillier, On P4-tidy graphs, Discrete Mathematics & Theoretical Computer Science, vol.1, issue.1, pp.17-41, 1997.
URL : https://hal.archives-ouvertes.fr/hal-00955688

M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics . Elsevier Science B.V, vol.57, 2004.

R. J. Gould, A look at cycles containing specified elements of a graph, Discrete Mathematics, vol.309, issue.21, pp.6299-6311, 2009.
DOI : 10.1016/j.disc.2008.04.017

F. Harary and J. P. Hayes, Edge fault tolerance in graphs, Networks, vol.8, issue.2, pp.135-142, 1993.
DOI : 10.1002/net.3230230207

G. R. Hendry, Extending cycles in graphs, Discrete Mathematics, vol.85, issue.1, pp.59-72, 1990.
DOI : 10.1016/0012-365X(90)90163-C

C. Ho and R. Lee, Counting clique trees and computing perfect elimination schemes in parallel, Information Processing Letters, vol.31, issue.2, pp.61-68, 1989.
DOI : 10.1016/0020-0190(89)90070-7

T. Ho, C. Lin, J. J. Tan, D. F. Hsu, and L. Hsu, On the extremal number of edges in hamiltonian connected graphs, Applied Mathematics Letters, vol.23, issue.1, pp.26-29, 2010.
DOI : 10.1016/j.aml.2009.03.025

W. Hochstättler and G. Tinhofer, Hamiltonicity in graphs with few P4 s. Computing, pp.213-225, 1995.

S. Hsieh, G. Chen, and C. Ho, Fault-free Hamiltonian cycles in faulty arrangement graphs, IEEE Transactions on Parallel and Distributed Systems, vol.10, issue.3, pp.223-237, 1999.
DOI : 10.1109/71.755822

D. F. Hsu, On container width and length in graphs, groups, and networks. IE- ICE Transactions Fundamentals of Electronics, Communications and Computer Sciences, issue.4, pp.77-668, 1994.

L. Hsu and C. Lin, Graph Theory and Interconnection Networks, 2009.

Z. Hu, F. Tian, and B. Wei, Hamilton connectivity of line graphs and claw-free graphs, Journal of Graph Theory, vol.89, issue.2, pp.130-141, 2005.
DOI : 10.1002/jgt.20099

P. Huang and L. Hsu, The spanning connectivity of line graphs, Applied Mathematics Letters, vol.24, issue.9, pp.1614-1617, 2011.
DOI : 10.1016/j.aml.2011.04.013

R. Hung and M. Chang, Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs, Applied Mathematics Letters, vol.24, issue.5, pp.648-652, 2011.
DOI : 10.1016/j.aml.2010.11.030

L. Ibarra, The clique-separator graph for chordal graphs, Discrete Applied Mathematics, vol.157, issue.8, pp.1737-1749, 2009.
DOI : 10.1016/j.dam.2009.02.006

K. Ioannidou, G. B. Mertzios, and S. D. Nikolopoulos, The Longest Path Problem has a Polynomial Solution on Interval Graphs, Algorithmica, vol.377, issue.2, pp.320-341, 2011.
DOI : 10.1007/s00453-010-9411-3

G. Isaak, Powers of Hamiltonian paths in interval graphs ISSN 1097-0118. doi: 10.1002/(SICI), 1<31::AID-JGT3>3.0.CO, pp.31-381097, 1998.

J. Jamrozik, R. Kalinowski, and Z. Skupie´nskupie´n, A catalogue of small maximal nonhamiltonian graphs, Discrete Mathematics, vol.39, issue.2, pp.229-234, 1982.
DOI : 10.1016/0012-365X(82)90145-5

S. Jo, J. Park, and K. Chwa, Paired many-to-many disjoint path covers in faulty hypercubes, Theoretical Computer Science, vol.513, pp.1-24, 2013.
DOI : 10.1016/j.tcs.2013.10.008

H. Jung, On a class of posets and the corresponding comparability graphs, Journal of Combinatorial Theory, Series B, vol.24, issue.2, pp.125-133, 1978.
DOI : 10.1016/0095-8956(78)90013-8

J. Karaganis, On the cube of a graph, Bulletin canadien de math??matiques, vol.11, issue.0, pp.295-296, 1968.
DOI : 10.4153/CMB-1968-037-0

H. A. Kierstead, G. N. Sárközy, and S. M. Selkow, On k???ordered Hamiltonian graphs, 1<17::AID-JGT2>3.0.CO, pp.17-25, 1999.
DOI : 10.1002/(SICI)1097-0118(199909)32:1<17::AID-JGT2>3.3.CO;2-7

L. M. Kirousis and D. M. Thilikos, The Linkage of a Graph, SIAM Journal on Computing, vol.25, issue.3, pp.626-647, 1996.
DOI : 10.1137/S0097539793255709

D. Kratsch and L. Stewart, Domination on Cocomparability Graphs, SIAM Journal on Discrete Mathematics, vol.6, issue.3, pp.400-417, 1993.
DOI : 10.1137/0406032

D. Kratsch, T. Kloks, and H. Müller, Computing the toughness and the scattering number for interval and other graphs, INRIA Rennes, 1994.
URL : https://hal.archives-ouvertes.fr/inria-00074433

D. Kratsch, J. Lehel, and H. Müller, Toughness, hamiltonicity and split graphs, Discrete Mathematics, vol.150, issue.1-3, pp.231-245, 1996.
DOI : 10.1016/0012-365X(95)00190-8

H. Lai and Y. Shao, -Hamiltonian Line Graphs, Journal of Graph Theory, vol.89, issue.3, pp.344-358, 2013.
DOI : 10.1002/jgt.21713
URL : https://hal.archives-ouvertes.fr/hal-01009120

H. Lai, Y. Liang, and Y. Shao, Hamiltonian Connected Line Graphs, Discrete Mathematics, vol.308, issue.18, pp.4293-4297, 2008.
DOI : 10.1007/978-3-540-72588-6_61

D. Larman and P. Mani, On the existence of certain configurations within graphs and the 1-skeleons of polytopes, Proceedings of the London Mathematical Society, vol.20, pp.144-160, 1974.

J. Lee and J. Park, General-demand disjoint path covers in a graph with faulty elements, International Journal of Computer Mathematics, vol.33, issue.10, pp.606-617, 2012.
DOI : 10.1016/j.ipl.2004.05.013

P. Li and Y. Wu, Maximal Neighborhood Search and Rigid Interval Graphs, Journal of Graph Algorithms and Applications, vol.17, issue.3, pp.245-264, 2013.
DOI : 10.7155/jgaa.00293

P. Li and Y. Wu, A linear time algorithm for the 1-fixed-endpoint path cover problem on interval graphs. submitted, 2014

D. Lick and A. White, $k$-degenerate graphs, Journal canadien de math??matiques, vol.22, issue.0, pp.1082-1096, 1970.
DOI : 10.4153/CJM-1970-125-1

C. Lin, H. Huang, and L. Hsu, On the spanning connectivity of graphs, Discrete Mathematics, vol.307, issue.2, pp.285-289, 2007.
DOI : 10.1016/j.disc.2006.06.021

C. Lin, H. Huang, J. J. Tan, and L. Hsu, On spanning connected graphs, Discrete Mathematics, vol.308, issue.7, pp.1330-1333, 2008.
DOI : 10.1016/j.disc.2007.03.072

C. Lin, J. J. Tan, D. F. Hsu, and L. Hsu, On the spanning fan-connectivity of graphs, Discrete Applied Mathematics, vol.157, issue.7, pp.1342-1348, 2009.
DOI : 10.1016/j.dam.2008.11.014

W. Mader, Homomorphieeigenschaften und mittlere Kantendichte von Graphen, Mathematische Annalen, vol.153, issue.215, pp.265-268, 1967.
DOI : 10.1007/BF01364272

G. K. Manacher, T. A. Mankus, and C. J. Smith, An optimum ??(n log n) algorithm for finding a canonical hamiltonian path and a canonical hamiltonian circuit in a set of intervals, Information Processing Letters, vol.35, issue.4, pp.205-211, 1990.
DOI : 10.1016/0020-0190(90)90025-S

M. M. Matthews and D. P. Sumner, Hamiltonian results inK1,3-free graphs, Journal of Graph Theory, vol.82, issue.1, pp.139-146, 1984.
DOI : 10.1002/jgt.3190080116

G. B. Mertzios and D. G. , A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs, SIAM Journal on Discrete Mathematics, vol.26, issue.3, pp.940-963
DOI : 10.1137/100793529

?. S. Miklavi? and P. Sparl, Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups, Journal of Graph Theory, vol.40, issue.4
DOI : 10.1002/jgt.20621

J. Moon, On a problem of Ore. The Mathematical Gazette, pp.40-41, 1965.

L. Ng and M. Schultz, k-Ordered Hamiltonian graphs ISSN 1097-0118. doi: 10.1002/(SICI), 1<45::AID-JGT6>3.0.CO, pp.45-571097, 1997.

D. J. Oberly and D. P. Sumner, Every connected, locally connected nontrivial graph with no induced claw is hamiltonian, Journal of Graph Theory, vol.98, issue.4, pp.351-356, 1979.
DOI : 10.1002/jgt.3190030405

O. Ore, Hamiltonian connected graphs, Journal de Mathématiques Pures et Appliquées Neuviéme Série, vol.42, pp.21-27, 1963.

K. Ozeki and T. Yamashita, Hamiltonian cycles and dominating cycles passing through a linear forest, Discrete Mathematics, vol.309, issue.6, pp.1584-1592, 2009.
DOI : 10.1016/j.disc.2008.02.031

B. Panda and S. K. Das, A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs, Information Processing Letters, vol.109, issue.18, pp.1041-1046, 2009.
DOI : 10.1016/j.ipl.2009.06.011

J. Park and I. Ihm, Single-source three-disjoint path covers in cubes of connected graphs, Information Processing Letters, vol.113, issue.14-16, pp.14-16527, 2013.
DOI : 10.1016/j.ipl.2013.04.012

J. Park, H. Kim, and H. Lim, Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements, IEEE Transactions on Parallel and Distributed Systems, vol.17, issue.3, pp.227-240, 2006.
DOI : 10.1109/TPDS.2006.37

L. Pósa, On the circuits of finite graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl, vol.8, pp.355-361, 1964.

A. Raychaudhuri, On powers of interval and unit interval graphs, Congressus Numerantium, vol.59, pp.235-242, 1987.

F. S. Roberts, Indifference graphs, Proof Techniques in Graph Theory, pp.139-146, 1969.

N. Robertson and P. Seymour, Graph Minors .XIII. The Disjoint Paths Problem, Journal of Combinatorial Theory, Series B, vol.63, issue.1, pp.65-110, 1995.
DOI : 10.1006/jctb.1995.1006
URL : http://doi.org/10.1006/jctb.1999.1919

E. Sabir and E. Vumar, Spanning connectivity of the power of a graph and Hamilton-connected index of a graph. Graphs and Combinatorics, pp.1551-1563, 2014.

V. Saenpholphat, F. Okamoto, and P. Zhang, Measures of traceability in graphs, Mathematica Bohemica, vol.131, issue.1, pp.63-84, 2006.

A. Saito, Chv??tal???Erd??s Theorem: Old Theorem with New Aspects, Computational Geometry and Graph Theory, pp.191-200, 2008.
DOI : 10.1002/jgt.3190120211

C. Savage, A Survey of Combinatorial Gray Codes, SIAM Review, vol.39, issue.4, pp.605-629, 1997.
DOI : 10.1137/S0036144595295272

M. Sekanina, On an ordering of the set of vertices of a connected graph. Publication of the Faculty of Sciences of the University of Brn?, pp.137-142, 1960.

W. Shih, T. C. Chern, and W. Hsu, An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs, SIAM Journal on Computing, vol.21, issue.6, pp.1026-1046, 1992.
DOI : 10.1137/0221061

B. A. Sørensen and C. Thomassen, On k-rails in graphs, Journal of Combinatorial Theory, Series B, vol.17, issue.2, pp.143-159, 1974.
DOI : 10.1016/0095-8956(74)90082-3

H. Su, Y. Shih, and S. Kao, On the 1-fault hamiltonicity for graphs satisfying Ore??s theorem, Information Processing Letters, vol.112, issue.21, pp.839-843, 2012.
DOI : 10.1016/j.ipl.2012.07.014

G. Wiener and M. Araya, On planar hypohamiltonian graphs, Journal of Graph Theory, vol.55, issue.1, pp.55-68, 2011.
DOI : 10.1002/jgt.20513

D. R. Woodall, List colourings of graphs, pp.269-301, 2001.
DOI : 10.1017/CBO9780511721328.012

Y. Wu, Z. Xiang, and Y. Zhu, Hamiltonian thickness and fault-tolerant spanning rooted path systems of graphs, 2015.