A service points location problem with Min-Max distance optimality criterion
We obtain a sharp upper bound for the spectral radius of a nonnegative matrix. This result is used to present upper bounds for the adjacency spectral radius, the Laplacian spectral radius, the signless Laplacian spectral radius, the distance spectral radius, the distance Laplacian spectral radius, the distance signless Laplacian spectral radius of an undirected graph or a digraph. These results are new or generalize some known results.
Caporossi, Chasser and Furtula in [Les Cahiers du GERAD (2009) G-2009-64] conjectured that the distance energy of a complete multipartite graph of order n with r ≥ 2 parts, each of size at least 2, is equal to 4(n − r). Stevanovic, Milosevic, Hic and Pokorny in [MATCH Commun. Math. Comput. Chem. 70 (2013), no. 1, 157-162.] proved the conjecture, and then Zhang in [Linear Algebra Appl. 450 (2014), 108-120.] gave another proof. We give a shorter proof of this conjecture using the interlacing inequalities...
A connected dominating set of a graph G = (V,E) is a subset of vertices CD ⊆ V such that every vertex not in CD is adjacent to at least one vertex in CD, and the subgraph induced by CD is connected. We show that, given an arc family F with endpoints sorted, a minimum-cardinality connected dominating set of the circular-arc graph constructed from F can be computed in O(|F|) time.
In 1932 Whitney showed that a graph with order is 2-connected if and only if any two vertices of are connected by at least two internally-disjoint paths. The above result and its proof have been used in some Graph Theory books, such as in Bondy and Murty’s well-known Graph Theory with Applications. In this note we give a much simple proof of Whitney’s Theorem.
Digraphs in which ordered pairs of out- and in-degrees of vertices are mutually distinct are called irregular, see Gargano et al. [3]. Our investigations focus on the problem: what are possible sizes of irregular digraphs (oriented graphs) for a given order n? We show that those sizes in both cases make up integer intervals. The extremal sizes (the endpoints of these intervals) are found in [1,5]. In this paper we construct, with help of Sokoban-type game, n-vertex irregular oriented graphs (irregular...
Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions is still unknown....