All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 4 Next

Displaying 61 – 80 of 135

Showing per page

Nonempty intersection of longest paths in a graph with a small matching number

Fuyuan Chen (2015)

Czechoslovak Mathematical Journal

A maximum matching of a graph G is a matching of G with the largest number of edges. The matching number of a graph G , denoted by α ' ( G ) , is the number of edges in a maximum matching of G . In 1966, Gallai conjectured that all the longest paths of a connected graph have a common vertex. Although this conjecture has been disproved, finding some nice classes of graphs that support this conjecture is still very meaningful and interesting. In this short note, we prove that Gallai’s conjecture is true for...

Non-hyperbolicity in random regular graphs and their traffic characteristics

Gabriel Tucci (2013)

Open Mathematics

In this paper we prove that random d-regular graphs with d ≥ 3 have traffic congestion of the order O(n logd−13 n) where n is the number of nodes and geodesic routing is used. We also show that these graphs are not asymptotically δ-hyperbolic for any non-negative δ almost surely as n → ∞.

Nordhaus-Gaddum-Type Results for Resistance Distance-Based Graph Invariants

Kinkar Ch. Das, Yujun Yang, Kexiang Xu (2016)

Discussiones Mathematicae Graph Theory

Two decades ago, resistance distance was introduced to characterize “chemical distance” in (molecular) graphs. In this paper, we consider three resistance distance-based graph invariants, namely, the Kirchhoff index, the additive degree-Kirchhoff index, and the multiplicative degree-Kirchhoff index. Some Nordhaus-Gaddum-type results for these three molecular structure descriptors are obtained. In addition, a relation between these Kirchhoffian indices is established.

Note on a conjecture for the sum of signless Laplacian eigenvalues

Xiaodan Chen, Guoliang Hao, Dequan Jin, Jingjian Li (2018)

Czechoslovak Mathematical Journal

For a simple graph G on n vertices and an integer k with 1 ≤ k ≤ n , denote by 𝒮 k + ( G ) the sum of k largest signless Laplacian eigenvalues of G . It was conjectured that 𝒮 k + ( G ) ≤ e ( G ) + k + 1 2 , where e ( G ) is the number of edges of G . This conjecture has been proved to be true for all graphs when k ∈ { 1 , 2 , n - 1 , n } , and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all k ). In this note, this conjecture is proved to be true for all graphs when k = n - 2 , and for some new classes of graphs.

Currently displaying 61 – 80 of 135