Let be a nontrivial connected graph on which is defined a coloring , , of the edges of , where adjacent edges may be colored the same. A path in is a rainbow path if no two edges of are colored the same. The graph is rainbow-connected if contains a rainbow path for every two vertices and of . The minimum for which there exists such a -edge coloring is the rainbow connection number of . If for every pair of distinct vertices, contains a rainbow geodesic, then is...
Let be a finite graph with an eigenvalue of multiplicity . A set of vertices in is called a star set for in if is not an eigenvalue of the star complement which is the subgraph of induced by vertices not in . A vertex subset of a graph is -regular if it induces a -regular subgraph and every vertex not in the subset has neighbors in it. We investigate the graphs having a -regular set which induces a star complement for some eigenvalue. A survey of known results is provided...
The concept of a route system was introduced by the present author in [3].Route systems of a connected graph generalize the set of all shortest paths in . In this paper some properties of route systems are studied.
The well known types of routes in graphs and directed graphs, such as walks, trails, paths, and induced paths, are characterized using axioms on vertex sequences. Thus non-graphic characterizations of the various types of routes are obtained.