位置：成果数据库 > 期刊 > 期刊详情页
奇图的匹配可扩性
  • ISSN号：1003-3998
  • 期刊名称：数学物理学报
  • 时间：0
  • 页码：365-372
  • 分类：O157.5[理学—数学;理学—基础数学]
  • 作者机构：[1]厦门大学数学科学学院,福建厦门361005, [2]厦门理工学院数理系,福建厦门361024
  • 相关基金：基金项目：国家自然科学基金（10831001）和福建省教育厅科技项目（JA08223）资助
  • 相关项目：应用图论
作者： 翟绍辉|郭晓峰|
关键词： (n, k, d)-图, k-可扩图, 几乎k-可扩图, n-因子临界图., （n, k, d）-graphs, k-extendable graphs, Near k-extendable graphs, n-factor-critical graphs.
中文摘要：

设G是一个图，n，k和d是三个非负整数，满足n＋2k＋d≤｜V（G）｜-2，｜V（G）｜和n＋d有相同的奇偶性．如果删去G中任意n个点后所得的图有k-匹配，并且任-k-匹配都可以扩充为一个亏d-匹配，那么称G是一个（n，k，d）-图．Liu和yu首先引入了（n，k，d）-图的概念，并且给出了（n，k，d）-图的一个刻划和若干性质．（0，k，1）．图也称为几乎k-可扩图．在本文中，作者改进了（n，k，d）-图的刻划，并给出了几乎k-可扩图和几乎k-可扩二部图的刻划，进而研究了几乎k-可扩图与n-因子临界图之间的关系．

英文摘要：

Let G be a graph, and let n, k and d be three nonnegative integers such that n＋2k＋ d ≤ ｜V（G） ｜ - 2 and, ｜V（G） ｜ and n ＋ d have the same parity. If after deleting any n vertices from G the remaining subgraph of G contains an k-matching and each k-matching of the subgraph can be extended to a defect-d-matching of the subgraph, then G is called an （n, k, d）-graph. Liu and Yu first introduced （n, k, d）-graphs, and gave some properties and characterization of （n, k, d）-graphs. A （0, k, 1）-graph may be also called a near k-extendable graph. In the present paper, the authors improve the characterization of （n, k, d）-graphs, and consequently obtain a characterization of near k-extendable graphs. Furthermore, a characterization of near k-extendable bipartite graphs and the relations between near k-extendable graphs and n-factor critical graphs are investigated.

同期刊论文项目
应用图论
期刊论文 159 获奖 1 著作 2
同项目期刊论文
Dimer statistics on the Klein bottle
Dimer statistics of honeycomb lattices on Klein bottle, Mobius strip and cylinder
The Laplacian energy of random graphs
On the similarity/dissimilarity of DNA sequences based on 4D graphical representation
On the minimal energy of trees with a given number of vertices of degree two
A Note on Path-Matchings
The graph of perfect matching polytope and an extreme problem
A novel characterization of n-extendable bipartite graphs
Smallest generalized cuts and diameter-increasing sets of Johnson graphs
DETERMINING THE COMPONENT NUMBER OF LINKS CORRESPONDING TO TRIANGULAR AND HONEYCOMB LATTICES
On plane graphs with link component number equal to the nullity
The atom-bond connectivity index of chemical unicyclic graphs
Small Randic Index Ordering of Trees with k Pendant Vertices
Zeros of the Jones Polynomial for Multiple Crossing-Twisted Links
Trees with a given order and matching number that have maximum general Randic index
PI index of toroidal polyhexes
Randic Index, Diameter and Average Distance
Direct Sum of Distributive Lattices on the Perfect Matchings of a Plane Bipartite Graph
Complete solution to a conjecture on Randic index
All Connected Graphs with Maximum Degree at Most 3 whose Energies are Equal to the Number of Vertice
Enumeration of perfect matchings of a type of quadratic lattice on the torus
On Triregular Graphs whose Energy Exceeds the Number of Vertices
Maximally resonant polygonal systems
Embedding on alphabet overlap digraphs
The Minimal Estrada Index of Trees with Two Maximum Degree Vertices
Extreme Atom-Bond Connectivity Index of Graphs
On a kind of reliability analysis of networks
l(1)-Embeddability of Hexagonal and Quadrilateral Mobius graphs
Models of virus capsids containing 72 pentameric capsomeres
The HOMFLY Polynomial for a Family of Polyhedral Links
On the restricted matching extension of graphs in surfaces
On forcing matching number of boron-nitrogen fullerene graphs
The architecture and the Jones polynomial of polyhedral links
Character of Trees with Extreme Balaban Index
Connectivity and minimal distance spectral radius of graphs
Bounding the sum of powers of the Laplacian eigenvalues of graphs
Dimers Belonging to Three Orientations on Plane Honeycomb Lattices
New Nordhaus-Gaddum-type results for the Kirchhoff index
A New Euler's Formula for DNA Polyhedra
Advances of Clar's Aromatic Sextet Theory and Randic´'s Conjugated Circuit Model
2-extendability and k-resonance of non-bipartite Klein-bottle polyhexes
The optimal strong radius and optimal strong diameter of the Cartesian product graphs
Removable Edges in Cycles of a k-Connected Graph
On the location of zeros of the Homfly polynomial
Embeddability of open-ended carbon nanotubes in hypercubes
Note on the energy of regular graphs
The Homfly Polynomial for Even Polyhedral Links
Forcing matching numbers of fullerene graphs
Note on Conjugated Unicyclic Graphs with Minimal Energy
On a Relation Between Randic Index and Chromatic number
Topological transformation of dual polyhedral links
BOUNDS ON THE PATH-MATCHING NUMBER
Various energies of random graphs
Maximal resonance of cubic bipartite polyhedral graphs
A general sufficient condition for a graph G with lambda (m) (G) a (c) 1/2 zeta (m) (G)
2-resonance of plane bipartite graphs and its applications to boron-nitrogen fullerenes
Note on Bipartite Unicyclic Graphs of Given Bipartition with Minimal Energy
Counting the Cyclocized Polyphenacenes
Super connectivity of Kronecker products of graphs
Contractible edges of k-connected graphs for k=4, 5
A kind of conditional fault tolerance of (n, k)-star graphs
REMOVABLE EARS OF 1-EXTENDABLE GRAPHS
ORIENTED STATE MODEL OF THE JONES POLYNOMIAL AND ITS CONNECTION TO THE DICHROMATIC POLYNOMIAL
A lower bound on the number of removable ears of 1-extendable graphs
The complexity of Platonic and Archimedean polyhedral links
Transfer-matrix Calculation of the Clar Covering Polynomial of Hexagonal Systems
The Architecture and Jones Polynomials of Cycle-crossover Polyhedral Links
Some results on Laplacian spectral radius of graphs with cut vertices
Hypoenergetic and Strongly Hypoenergetic k-Cyclic Graphs
A combination of Clar number and Kekul, count as an indicator of relative stability of fullerene iso
Character of Graphs with Extremal Balaban Index
ON COMPUTING KAUFFMAN BRACKET POLYNOMIAL OF MONTESINOS LINKS
The architecture of polyhedral links and their HOMFLY polynomials
On super 2-restricted and 3-restricted edge-connected vertex transitive graphs
Topological Analysis of Enzymatic Actions on DNA Polyhedral Links
A proof of a conjecture on the Randic index of graphs with given girth
Degree conditions for graphs to be lambda(3)-optimal and super-lambda(3)
Characterizations for P(>= 2)-factor and P(>= 3)-factor covered graphs
Extended Goldberg polyhedral links with odd tangles
Johnson图的哈密尔顿连通性、泛圈性和删边保持直径不变性
The Laplacian spectral radius of unicyclic graphs with k pendent vertices
Connectivity of the Mycielskian of a digraph
(n,m)-Graphs with maximum zeroth-order general Randic index for alpha in (-1,0)
A novel molecular design of polyhedral links and their chiral analysis
All hypoenergetic graphs with maximum degree at most 3
Hosoya Polynomials of TUC4C8® Nanotubes
The maximum Randic index of chemical trees with k pendants
Bicyclic graphs with extremal Kirchhoff index
Some graphs determined by their spectra
Extremal fullerene graphs with the maximum Clar number
Enumerating spanning trees of graphs with an involution
ON k-RESONANT FULLERENE GRAPHS
Algorithms and extremal problem on Wiener polarity index
Complete solution to a conjecture on the Randic index of triangle-free graphs
Optimal strong (k, d)-orientation of complete k-partite graphs
Lower and upper orientable strong diameters of graphs satisfying the Ore condition
Minimal 2-matching-covered graphs
Kirchhoff index of composite graphs
2-extendability of toroidal polyhexes and Klein-bottle polyhexes
On f-fault tolerant arc-forwarding and optical indices of all-optical folded hypercubes
Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes
The atom-bond connectivity index of chemical bicyclic graphs
On Vertex-Distinguishing Proper Edge Colorings of Graphs Satisfying the Ore Condition
Note on unicyclic graphs with given number of pendent vertices and minimal energy
Extended Goldberg polyhedral links with even tangles
化学单圈图的原子键连通性指数(英文)
On the Distance Spectra and Energies of Cartesian Product of Some Graphs
Some rules on resistance distance with applications
GRAPHICAL CALCULI FOR THE DUBROVNIK POLYNOMIAL WITH APPLICATIONS
The Braid Index of Complicated DNA Polyhedral Links
On the Anti-Kekule Number of Fullerenes
Super lambda(3)-optimality of regular graphs
Enumerating the total colorings of a polyhedron and application to polyhedral links
On the characterizing properties of the permanental polynomials of graphs
Super-connectivity of Kronecker products of split graphs, powers of cycles, powers of paths and comp
The number of Kekule structures of polyominos on the torus
Dimer coverings on random multiple chains of planar honeycomb lattices
Hosoya polynomials of the capped zig-zag nanotubes
Wiener Index in Random Polyphenyl Chains
Super Connectivity and Super Edge Connectivity of the Mycielskian of a Graph
On the restricted matching extension of graphs on the torus and the Klein bottle
Computing the permanental polynomials of bipartite graphs by Pfaffian orientation
THE HOMFLY AND DICHROMATIC POLYNOMIALS
Global Forcing Number of Some Chemical Graphs
Hexagonal resonance of (3,6)-fullerenes
若干与统计物理相关的组合问题
基于4D图形表示的DNA序列相似性分析
极大3-限制性边连通图的若干充分条件
关于Randic指数及图的直径
期刊信息
  • 《数学物理学报：A辑》
  • 北大核心期刊（2011版）
  • 主管单位:中国科学院
  • 主办单位:中国科学院武汉物理与数学研究所
  • 主编：李邦河 陈贵强 朱熹平
  • 地址：湖北省武汉市武昌小洪山西路30号武汉71010信箱
  • 邮编：430071
  • 邮箱：actams@wipm.ac.cn
  • 电话：027-87199206
  • 国际标准刊号：ISSN：1003-3998
  • 国内统一刊号：ISSN：42-1226/O
  • 邮发代号:38-214
  • 获奖情况:
  • 国内外数据库收录:
  • 俄罗斯文摘杂志,美国数学评论（网络版）,德国数学文摘,日本日本科学技术振兴机构数据库,中国中国科技核心期刊,中国北大核心期刊（2004版）,中国北大核心期刊（2008版）,中国北大核心期刊（2011版）,中国北大核心期刊（2014版）,中国北大核心期刊（2000版）
  • 被引量:5382