Spectra of unicyclic graphs

Unicyclic graphs are discussed in the context of graph orderings related to eigenvalues. Several theorems involving lexicographical ordering by spectral moments as well as the ordering by the largest eigenvalue are proved. An appendix contains a table of the 89 unicyclic graphs on eight vertices together with their spectra, spectral moments and characteristic polynomials.Carnegie Research Fellow, University of Stirling, 1985–86.     

Chromatic number and subtrees of graphs

Let G and H be two graphs. We say that G induces H if G has an induced subgraph isomorphic to H: A. Gyárfás and D. Sumner, independently, conjectured that, for every tree T. there exists a function f _T ; called binding function, depending only on T with the property that every graph G with chromatic number f _T (ω(G)) induces T. A. Gyárfás, E. Szemerédi and Z. Tuza confirmed the conjecture for all trees of radius two on triangle-free graphs, and H. Kierstead and S. Penrice generalized the approach and the conclusion of A. Gyárfás et al. onto general graphs. A. Scott proved an interesting topological version of this conjecture asserting that for every integer k and every tree T of radius r, every graph G with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(14 ^r-1(r - 1)!) times. We extend the approach of A. Gyárfás and present a binding function for trees obtained by identifying one end of a path and the center of a star. We also improve A. Scott's upper bound by modifying his subtree structure and partition technique, and show that for every integer k and every tree T of radius r, every graph with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(6 ^r?2) times.     

Stable and semi-stable unicyclic graphs

We show by a constructive proof, that if a unicyclic graph has a transposition in its automorphism group, then it is stable. Using a similar technique, we also determine which unicyclic graphs are not semi-stable.     

On super vertex-graceful unicyclic graphs

A graph G with p vertices and q edges, vertex set V(G) and edge set E(G), is said to be super vertex-graceful (in short SVG), if there exists a function pair (f, f ⁺) where f is a bijection from V(G) onto P, f ⁺ is a bijection from E(G) onto Q, f ⁺((u, v)) = f(u) + f(v) for any (u, v) ∈ E(G),

The largest eigenvalue of unicyclic graphs

Let G be a simple graph. Let λ₁(G) and μ₁(G) denote the largest eigenvalue of the adjacency matrix and the Laplacian matrix of G, respectively. Let Δ denote the largest vertex degree. If G has just one cycle, then

     

The spread of the unicyclic graphs

Let G be a simple connected graph with n vertices and n edges which we call a unicyclic graph. In this paper, we first investigate the least eigenvalue λ_n(G), then we present two sharp bounds on the spread s(G) of G.     

The Laplacian spread of unicyclic graphs

The Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the second-smallest eigenvalue of the Laplacian matrix of the graph. In a recent work the trees with maximal Laplacian spread and with minimal Laplacian spread among all trees of fixed order are separately determined. In this work, we characterize the unique unicyclic graph with maximal Laplacian spread among all connected unicyclic graphs of fixed order.     

Random subtrees and unimodal sequences in graphs

For a complete graph $K_n$ and a nonnegative integer k, we study the probability that a random subtree of $K_n$ has exactly $n-k$ vertices and show that it approaches a limiting value of $\frac{e^{-k-e^{-1}}}{k!}$ as n tends to infinity. We also consider the (conditional) probability that a random subtree of $K_n$ contains a given edge, and more generally, a fixed subtree. In particular, if e and f are adjacent edges of $K_n$, Chin, Gordon, MacPhee and Vincent [J. Graph Theory 89 (2018), 413-438] conjectured that $P[e\subseteq T|f\subseteq T]\le P[e\subseteq T]$. We prove this conjecture and further prove that $P[e\subseteq T|f\subseteq T]$ tends to three-quarters of $P[e\subseteq T]$ as $n\to \infty$. Finally, several classes of graphs are given, such as star plus an edge, lollipop graph and glasses graph, whose subtree polynomials are unimodal.     

Induced subtrees in graphs of large chromatic number

Our paper proves special cases of the following conjecture: for any fixed tree T there exists a natural number f = f (T) to that every triangle-free graph of chromaticnumber f(T) contains T as an induced subgraph. The main result concerns the case when T has radius two.     

On the edge multicoloring of unicyclic graphs

A multicoloring of an edge weighted graph is an assignment of intervals to its edges so that the intervals of adjacent edges do not intersect at interior points and the length of each interval is equal to the weight of the edge. The minimum length of the union of all intervals is called an edge multichromatic number of the graph. The maximum weighted degree of a vertex (i.e., the sum of the weights of all edges incident with it) is an evident lower bound of this number. There are available the examples in which the multichromatic number is one and a half times larger than the lower bound. Also, there is a conjecture that the bound cannot exceeded by a larger factor. Here we prove this conjecture for the class of unicyclic graphs.     

The intersection graphs of subtrees in trees are exactly the chordal graphs

The intersection graph of a family of subtrees in an undirected tree is called a subtree graph. A graph is called chordal if every simple circuit with more than three vertices has an edge connecting two non-consecutive vertices. In this paper, we prove that, for a graph G, the following conditions are equivalent: (i) G is a chordal graph; (ii) G is a subtree graph; (iii) G is a proper subtree graph.Consider a chordal graph G. We give an efficient algorithm for constructing a representation of G by a family of subtrees in a tree.     

The minimum Laplacian spread of unicyclic graphs

The Laplacian spread of a graph [1] is defined as the difference between the largest eigenvalue and the second-smallest eigenvalue of the associated Laplacian matrix. In this paper, the minimum Laplacian spread of unicyclic graphs with given order is determined.     

单圈图的代数连通度的排序

n阶图G称为是一个单圈图,如果G是连通的,并且G的边数也是n.用U(n)表示所有n阶单圈图所成的集合.给出了当阶数n≥25时,代数连通度为前九大的n阶单圈图及它们的代数连通度.     

On the number of subtrees for almost all graphs

In this article it is shown that the number of common edges of two random subtrees of K_n having r and s vertices, respectively, has a Poisson distribution with expectation 2λμ if $\mathop {\lim }\limits_{n \to \infty } r/n = \lambda$ and $\mathop {\lim }\limits_{n \to \infty } s/n = \mu$. Also, some estimations of the number of subtrees for almost all graphs are made by using Chebycheff's inequality. © 1994 John Wiley & Sons, Inc.     

Constant tolerance intersection graphs of subtrees of a tree

A chordal graph is the intersection graph of a family of subtrees of a host tree. In this paper we generalize this. A graph G=(V,E) has an (h,s,t)-representation if there exists a host tree T of maximum degree at most h, and a family of subtrees {S_v}_v∈V of T, all of maximum degree at most s, such that uv∈E if and only if |S_u∩S_v|?t. For given h,s, and t, there exist infinitely many forbidden induced subgraphs for the class of (h,s,t)-graphs. On the other hand, for fixed h?s?3, every graph is an (h,s,t)-graph provided that we take t large enough. Under certain conditions representations of larger graphs can be obtained from those of smaller ones by amalgamation procedures. Other representability and non-representability results are presented as well.