检索结果-内蒙古大学图书馆

Forbidden subgraphs in connected graphs

THEORETICAL COMPUTER SCIENCE 2004年第1-2期314卷 121-171页

作者： Ravelomanana, V Thimonier, LS Univ Paris 13 LIPN UMR 7030 F-93430 Villetaneuse France Univ Picardie LaRIA EA 2083 F-80000 Amiens France

Given a set xi = {H-1, H-2,...} of connected non-acyclic graphs, a xi-free graph is one which does not contain any member of as copy. Define the excess of a graph as the difference between its number of edges and its number of vertices. Let (W) over cap (k,xi) be the exponential generating function (EGF for brief) of connected xi-free graphs of excess equal to k (k greater than or equal to 1). For each fixed, a fundamental differential recurrence satisfied by the EGFs (W) over cap (k,xi) is derived. We give methods on how to solve this nonlinear recurrence for the first few values of k by means of graph surgery. We also show that for any finite collection xi of non-acyclic graphs, the EGFs (W) over cap (k,xi) are always rational functions of the generating function, T, of Cayley's rooted (non-planar) labelled trees. From this, we prove that almost all connected graphs with n nodes and n + k edges are xi-free, whenever k = o(n(1/3)) and \xi\ < infinity by means of Wright's inequalities and saddle point method. Limiting distributions are derived for sparse connected xi-free components that are present when a random graph on n nodes has approximately n/2 edges. In particular, the probability distribution that it consists of trees, unicyclic components,...,(q + 1)-cyclic components all xi-free is derived. Similar results are also obtained for multigraphs, which are graphs where self-loops and multiple-edges are allowed. (C) 2003 Elsevier B.V. All rights reserved.

关键词： combinatorial problems enumerative combinatorics analytic combinatorics labelled graphs multivariate generating functions asymptotic enumeration random graphs triangle-free graphs

来源：评论

学校读者我要写书评

暂无评论

Patchworks and metablocks enumeration

引用

INFORMATION PROCESSING LETTERS 2000年第3-4期73卷 77-86页

作者： Ravelomanana, V Thimonier, L Univ Picardie LaRIA F-80000 Amiens France

A cutpoint of a graph is a point whose removal increases the number of connected components. A block graph is connected, not reduced to a point and has no cutpoint. A cutedge is the association of an edge and his two adjacent vertices such that their removal increase the number of components. The graphs considered here specify the notion of blocks. We call metablock a connected graph with no cutpoint and no cutedge. A graphical patchwork is a graph without a cutpoint but with at least one cutedge. We show here how to enumerate labeled metablocks and patchworks by obtaining their exponential generating functions according to their number of edges and vertices. This problem is quite interesting because of its originality. A particular consequence is the observation that almost all graphs are patchworks. (C) 2000 Published by Elsevier Science B.V. All rights reserved.

关键词： combinatorial problems enumerative combinatorics labeled connected graphs multivariate generating functions

来源：评论

学校读者我要写书评

暂无评论

ADDITION

引用

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY 1977年第FEB期226卷 393-394页

作者： SRIVASTAVA, HM Department of Mathematics University of Victoria Victoria BC V8W 2Y2 Canada Department of Mathematics and Statistics University of Guelph Guelph ON NIG 2W1 Canada

Abstract: Certain constraints are explicitly specified for the validity of a recent result involving a multivariate generating function, due to the present authors [1, p. 369, Theorem 6]. It is also indicated ... 详细信息

关键词： Complex parameters multivariate generating functions (multidimensional) polynomial sequences

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：