Rao Li (University of South Carolina at Aiken, USA)

Copyright: © 2020
|Pages: 15

DOI: 10.4018/978-1-5225-9380-5.ch006

Chapter Preview

TopWe consider only finite undirected graphs without loops or multiple edges. Notation and terminology not defined here follow that in Bondy and Murty (1976). Let be a graph. We use *n*, *e*, δ, and κ to denote the order, size, minimum degree, and connectivity of *G*, respectively. The complement of *G* is denoted by . We also use and to denote the complete graph and the empty graph of order *n*. The forgotten topological index of *G*, denoted , is defined as (see Furtala & Gutman, 2015). The second Zagreb index of *G*, denoted , is defined as (see Gutman et al., 1975). The hyper-Zagreb index of *G*, denoted , is defined as (see Milovanovic, Matejic & Milovanovic, 2019). We use to denote the largest eigenvalue of the adjacency matrix of a graph *G* of order *n*. For two disjoint graphs and , we use and to denote respectively the union and join of and . The concept of closure of a graph *G* was introduced by Bondy and Chvátal in Bondy and Chvatal (1976). The *k*-closure of a graph *G*, denoted , is a graph obtained from *G* by recursively joining two nonadjacent vertices such that their degree sum is at least *k* until no such pair remains. We use to denote the number of *r*-combinations of a set with *n* distinct elements. A cycle *C* in a graph *G* is called a Hamiltonian cycle of *G* if *C* contains all the vertices of *G*. A graph *G* is called Hamiltonian if *G* has a Hamiltonian cycle. A path *P* in a graph *G* is called a Hamiltonian path of *G* if *P* contains all the vertices of *G*. A graph *G* is called traceable if *G* has a Hamiltonian path. A graph *G* is *k*-Hamiltonian if for all with , the subgraph induced by is Hamiltonian. Clearly, G is 0-Hamiltonian if and only if *G* is Hamiltonian. A graph *G* is *k*-edge-Hamiltonian if any collection of vertex-disjoint paths with at most *k* edges is in a Hamiltonian cycle in *G*. Clearly, G is 0-edge-Hamiltonian if and only if *G* is Hamiltonian. A graph *G* is *k*-path-coverable if can be covered by *k* or fewer vertex-disjoint paths. Clearly, G is 1-path-coverable if and only *G* is a traceable. A graph *G* is *k*-connected if it has more than *k* vertices and *G* is still connected whenever fewer than *k* vertices are removed from G. A graph *G* is *k*-edge-connected if it has at least two vertices and *G* is still connected whenever fewer than *k* edges are removed from G.

Search this Book:

Reset

Copyright © 1988-2019, IGI Global - All Rights Reserved