On trees with real-rooted independence polynomial

The independence polynomial of a graph $G$ is

$I(G,x)=\sum _{k\ge 0}{i}_k\left(G\right)x^k,$

where $i_k\left(G\right)$ denotes the number of independent sets of $G$ of size $k$ (note that $i_0\left(G\right)=1$). In this paper we show a new method to prove real-rootedness of the independence polynomials of certain families of trees.In particular we will give a new proof of the real-rootedness of the independence polynomials of centipedes (Zhu’s theorem), caterpillars (Wang and Zhu’s theorem), and we will prove a conjecture of Galvin and Hilyard about the real-rootedness of the independence polynomial of the so-called Fibonacci trees.     

On the independence number of sparse graphs

Let G be a regular graph of degree d on n points which contains no K_r (r ≥ 4). Let α be the independence number of G. Then we show for large d that α ≥ c(r)n . © 1995 John Wiley & Sons, Inc.     

On the independence number of minimum distance graphs

Let F=F(n) denote the largest number such that any set of n points in the plane with minimum distance 1 has at least F elements, no two of which are at unit distance. Improving a result by Pollack, we show that F(n)≥ (9/35)n . We also give an O(n log n) time algorithm for selecting at least (9/35)n elements in a set of n points with minimum distance 1 so that no two selected points are at distance 1. <lsiheader> <onlinepub>7 August, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>20n2p179.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>no <sectionname> </lsiheader> Received June 12, 1996, and in revised form April 22, 1997.     

On the independence number of random cubic graphs

We show that as n→∞, the independence number α(G), for almost all 3-regular graphs G on n vertices, is at least (6 log(3/2) – 2 – ?)n, for any constant ?>0. We prove this by analyzing a greedy algorithm for finding independent sets. © 1994 John Wiley & Sons, Inc.     

Approximations to clustering and subgraph problems on trees

Given a tree with vertex weights, we derive fully polynomial approximation schemes for the following two NP-hard problems: (i) Partition the graph into connected cluster sets such that the weight of each set does not exceed a given bound and a monotone objective function is minimized. (ii) Find a subtree with bounded vertex weight such that a monotone objective function is maximized.     

On the chromatic number of a random subgraph of the Kneser graph

Results are obtained that substantially strengthen a previously known bound for the chromatic number of a random subgraph of the Kneser graph.     

On the linear independence of numbers over number fields

In the present paper, the problem of a lower bound for the measure of linear independence of a given collection of numbers ₁, , _n is considered under the assumption that, for a sequence of polynomials whose coefficients are algebraic integers, upper and lower estimates at the point ( ₁, , _n ) are known. We use a method that generalizes the Nesterenko method to the case of an arbitrary algebraic number field.Translated fromMatematicheskie Zametki, Vol. 64, No. 4, pp. 506–517, October, 1998.The author wishes to thank Professor Yu. V. Nesterenko for setting the problem and valuable advice and Professor D. Bertrand for fruitful discussions.This research was partially supported by the International Science Foundation (Soros Foundation) under grant No. 507_s.     

On the maximum number of edges in a c4-free subgraph of qn

For the maximum number f(n) of edges in a C₄-free subgraph of the n-dimensional cube-graph Q_n we prove f(n) ≥ 1/2(n +√n)2^n?1 for n = 4^r, and f(n) ≥ 1/2(n +0.9√n)2^n?1 for all n ≥ 9. This disproves one version of a conjecture of P. Erdos. © 1995 John Wiley & Sons, Inc.     

On the number of complementary trees in a graph

Consider a graph with no loops or multiple arcs with n+1 nodes and 2n arcs labeled a_l,…,a_n,a′_l,…,a′_n, where n ≥ 5. A spanning tree of such a graph is called complementary if it contains exactly one arc of each pair {a_i,a′_i}. The purpose of this paper is to develop a procedure for finding complementary trees in a graph, given one such tree. Using the procedure repeatedly we give a constructive proof that every graph of the above form which has one complementary tree has at least six such trees.     

On the number of trees in a random forest

The analytic methods of Pólya, as reported in [1, 6] are used to determine the asymptotic behavior of the expected number of (unlabeled) trees in a random forest of order p. Our results can be expressed in terms of η = .338321856899208 …, the radius of convergence of t(x) which is the ordinary generating function for trees. We have found that the expected number of trees in a random forest approaches 1 + Σ_k=1^∞t(η^k) = 1.755510 … and the form of this result is the same     

ON NUMBER OF LEAVES ANDBANDWIDTH OF TREES

1.IntroductionFOragraphG=(V,E)oforderp,aonetoonemappingfromVinto{l,2,',p}iscalledanumberingofG.Definition1.1.SupposefisanumberingofG.LetBj(G)=(u57teif(u)--f(v)l.ThebandwidthofG,denotedbyB(G),isdefinedbyB(G)=min{Bf(G)IfisanumberingofG}.Thebandwidthproblemofgraphshasbecomeveryimportantsincethemid-sixties(see[21or[4]).Itisverydifficulttodeterminethebandwidthofagraph.GareyetallllshowedthatthebandwidthproblemisNP-completeevenifitisrestrictedtotreeswithmaximumdegree3.Soitisinterestingtoe…     

On the number of minimal 1-Steiner trees

We count the number of nonisomorphic geometric minimum spanning trees formed by adding a single point to ann-point set ind-dimensional space, by relating it to a family of convex decompositions of space. TheO(n ^d log^{2d 2}−d n) bound that we obtain significantly improves previously known bounds and is tight to within a polylogarithmic factor. The research of D. Eppstein was performed in part while visiting Xerox PARC.     

On the maximum double independence number of Steiner triple systems

The maximum independence number of Steiner triple systems of order $v$ is well‐known. Motivated by questions of access balancing in storage systems, we determine the maximum total cardinality of a pair of disjoint independent sets of Steiner triple systems of order $v$ for all admissible orders.     

On the independence number of graphs related to a polarity

We investigate the independence number of two graphs constructed from a polarity of . For the first graph under consideration, the Erdős-Rényi graph , we provide an improvement on the known lower bounds on its independence number. In the second part of the paper, we consider the Erdős-Rényi hypergraph of triangles . We determine the exact magnitude of the independence number of , even. This solves a problem posed by Mubayi and Williford [On the independence number of the ErdŐs-RÉnyi and projective norm graphs and a related hypergraph, J. Graph Theory, 56 (2007), pp. 113-127, Open Problem 3].     

On thek-cut subgraph polytope

We consider the problem of finding a minimum-cost set ofk pairwise-disjoint (s, t)-cuts in a graph. For non-negative costs, this problem was solved independently by Nishihara and Inoue, and Wagner. Both solutions involve formulating the problem as a linear-programming problem. In this paper, we give new polyhedral interpretations of the problem. Relationships to the path formulation of the maximum-flow problem are also established.Corresponding author.     

On the Ramsey number of trees versus graphs with large clique number

Chvátal established that r(T_m, K_n) = (m – 1)(n – 1) + 1, where T_m is an arbitrary tree of order m and K_n is the complete graph of order n. This result was extended by Chartrand, Gould, and Polimeni who showed K_n could be replaced by a graph with clique number n and order n + 1 provided n ≧ 3 and m ≧ 3. We further extend these results to show that K_n can be replaced by any graph on n + 2 vertices with clique number n, provided n ≧ 5 and m ≧ 4. We then show that further extensions, in particular to graphs on n + 3 vertices with clique number n are impossible. We also investigate the Ramsey number of trees versus complete graphs minus sets of independent edges. We show that r(T_m, K_n –tK₂) = (m – 1)(n – t – 1) + 1 for m ≧ 3, n ≧ 6, where T_m is any tree of order m except the star, and for each t, O ≦ t ≦ [(n – 2)/2].