𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The 2-intersection number of paths and bounded-degree trees

✍ Scribed by Michael S. Jacobson; André E. Kézdy; Douglas B. West

Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
416 KB
Volume
19
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We represent a graph by assigning each vertex a finite set such that vertices are adjacent if and only if the corresponding sets have at least two common elements. The 2‐intersection number θ~2~(G) of a graph G is the minimum size of the union of sets in such a representation. We prove that the maximum order of a path that can be represented in this way using t elements is between (t^2^ ‐ 19__t__ + 4)/4 and (t^2^ ‐ t + 6)/4, making θ~2~(P~n~) asymptotic to 2√n. We also show the existence of a constant c depending on ϵ such that, for any tree T with maximum degree at most d, θ~2~(T) ≤ c(√n)^1+ϵ^. When the maximum degree is not bounded, there is an n‐vertex tree T with θ~2~(T) > .945__n__^2/3^. © 1995 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Maximizing the number of independent sub
Maximizing the number of independent subsets over trees with bounded degree
✍ Clemens Heuberger; Stephan G Wagner 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 208 KB 👁 1 views

## Abstract The number of independent vertex subsets is a graph parameter that is, apart from its purely mathematical importance, of interest in mathematical chemistry. In particular, the problem of maximizing or minimizing the number of independent vertex subsets within a given class of graphs has

The Color-Degree Matrix and the Number o
The Color-Degree Matrix and the Number of Multicolored Trees in Star Decompositions
✍ J.Q. Liu; A.J. Schwenk 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 473 KB

In a previous paper we investigated the problem of counting the number of multicolored spanning trees in biclique decompositions. In particular, for acyclic decompositions we found the minimum and maximum numbers of multicolored trees. We now introduce the color-degree matrix \(C\) and show that the

A Characterization of the degree sequenc
A Characterization of the degree sequences of 2-trees
✍ Prosenjit Bose; Vida Dujmovi; Danny Krizanc; Stefan Langerman; Pat Morin; David 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 260 KB 👁 1 views

## Abstract A graph __G__ is a 2‐tree if __G__ = __K__~3~, or __G__ has a vertex __v__ of degree 2, whose neighbors are adjacent, and __G__/ __v__ is a 2‐ tree. A characterization of the degree sequences of 2‐trees is given. This characterization yields a linear‐time algorithm for recognizing and r

Lower Bounds for the Energy of Unit Vect
Lower Bounds for the Energy of Unit Vector Fields and Applications: Volume 152, Number 2 (1998), pages 379–403
✍ Etienne Sandier 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 29 KB

A mistake in the proof of Theorem 1 occurred which was pointed out to the author by Tristan RivieÁ re. It is stated there that the constant C depends only on the domain and the H 1Â2 norm of the boundary data. It really should be the H s -norm for some s>1Â2 for the result to be correct. The proble

Volume 16, Number 2 (2000), in the artic
Volume 16, Number 2 (2000), in the article “A Phylogeny of the Trimeresurus Group of Pit Vipers: New Evidence from a Mitochondrial Gene Tree,” by Anita Malhotra and Roger S. Thorpe, pages 199–211 ()
📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 29 KB

In Table 1 on page 201, two GenBank accession numbers were misprinted. AF171889 (Trimeresurus cantori, 29th entry) should be AF171899, and AF17191 (Tropidolaemus wagleri, last line) should be AF171917.