NDLI: Enumeration of Equicolorable Trees

Please wait, while we are loading the content...

Enumeration of Equicolorable Trees

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Pippenger, Nicholas
Copyright Year	2001
Abstract	A tree, being a connected acyclic graph, can be bicolored in two ways, which differ from each other by exchange of the colors. We shall say that a tree is equicolorable if these bicolorings assign the two colors to equal numbers of vertices. Labelled equicolored trees have been enumerated several times in the literature, and from this result it is easy to enumerate labelled equicolorable trees. The result is that the probability that a randomly chosen n-vertex labelled tree is equicolorable is asymptotically just twice the probability that its vertices would be equicolored if they were assigned colors by independent unbiased coin flips. Our goal in this paper is the enumeration of unlabelled equicolorable trees (that is, trees up to isomorphism), both exactly (in terms of generating functions) and asymptotically. We treat both the rooted and unrooted versions of this problem and conclude that in either case the probability that a randomly chosen n-vertex unlabelled tree is equicolorable is asymptotically 1.40499... times as large as the probability that it would be equicolored if its vertices were assigned colors by independent unbiased coin flips.
Starting Page	93
Ending Page	115
Page Count	23
File Format	PDF
ISSN	08954801
DOI	10.1137/S0895480100368463
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	1
Volume Number	14
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-08-01
Access Restriction	Subscribed
Subject Keyword	Trees Exact enumeration problems, generating functions asymptotic enumeration generating functions Asymptotic enumeration
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Enumeration of Matchings in the Incidence Graphs of Complete and Complete Bipartite Graphs

Protection Number in Plane Trees

Correlation of GraphTheoretical Indices

Growing and Destroying Catalan-Stanley Trees

Enumeration of fully parked trees

Parking functions for trees and mappings

$k$-protected vertices in unlabeled rooted plane trees

The height of multiple edge plane trees

Pattern avoidance in labelled trees

Enumeration of Equicolorable Trees

Similar Documents

Enumeration of Matchings in the Incidence Graphs of Complete and Complete Bipartite Graphs

Protection Number in Plane Trees

Correlation of GraphTheoretical Indices

Growing and Destroying Catalan-Stanley Trees

Enumeration of fully parked trees

Parking functions for trees and mappings

$k$-protected vertices in unlabeled rooted plane trees

The height of multiple edge plane trees

Pattern avoidance in labelled trees

Enumeration of Equicolorable Trees