.
Near-minimal spanning trees : a scaling exponent in probability models
We study the relation between the minimal spanning tree (MST) on many random points and the “near-minimal” tree which is optimal subject to the constraint that a proportion δ of its edges must be different from those of the MST. Heuristics suggest that, regardless of details of the probability model, the ratio of lengths should scale as 1+Θ(δ2). We prove this scaling result in the model of the lattice with random edge-lengths and in the euclidean model.
New bounds on the Laplacian spectral ratio of connected graphs
Let be a simple connected undirected graph. The Laplacian spectral ratio of is defined as the quotient between the largest and second smallest Laplacian eigenvalues of , which is an important parameter in graph theory and networks. We obtain some bounds of the Laplacian spectral ratio in terms of the number of the spanning trees and the sum of powers of the Laplacian eigenvalues. In addition, we study the extremal Laplacian spectral ratio among trees with vertices, which improves some known...
Nichtbeweisbarkeit von gewissen kombinatorischen Eigenschaften endlicher Bäume.
Nonadmissible genealogical trees
Noncrossing trees and noncrossing graphs.
Nordhaus-Gaddum results for weakly convex domination number of a graph
Nordhaus-Gaddum results for weakly convex domination number of a graph G are studied.
Note on a theorem of J. Baumgartner
Note on linear arboricity
Note on linear arboricity
Note on linear arboricity of graphs with large girth
Note On The Game Colouring Number Of Powers Of Graphs
We generalize the methods of Esperet and Zhu [6] providing an upper bound for the game colouring number of squares of graphs to obtain upper bounds for the game colouring number of m-th powers of graphs, m ≥ 3, which rely on the maximum degree and the game colouring number of the underlying graph. Furthermore, we improve these bounds in case the underlying graph is a forest.
Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs
Let G1 and G2 be simple graphs and let n1 = |V (G1)|, m1 = |E(G1)|, n2 = |V (G2)| and m2 = |E(G2)|. In this paper we derive sharp upper and lower bounds for the number of spanning trees τ in the Cartesian product G1 □G2 of G1 and G2. We show that: [...] and [...] . We also characterize the graphs for which equality holds. As a by-product we derive a formula for the number of spanning trees in Kn1 □Kn2 which turns out to be [...] .
Nowhere-zero modular edge-graceful graphs
For a connected graph G of order n ≥ 3, let f: E(G) → ℤₙ be an edge labeling of G. The vertex labeling f’: V(G) → ℤₙ induced by f is defined as , where the sum is computed in ℤₙ. If f’ is one-to-one, then f is called a modular edge-graceful labeling and G is a modular edge-graceful graph. A modular edge-graceful labeling f of G is nowhere-zero if f(e) ≠ 0 for all e ∈ E(G) and in this case, G is a nowhere-zero modular edge-graceful graph. It is shown that a connected graph G of order n ≥ 3 is nowhere-zero...