摘要:

AbstractThe path layer matrix (or path degree sequence) of a graphGcontains quantitative information about all paths inG. The entry (i,j) in this matrix is the number of simple paths inGhaving initial vertexvand lengthj.It was known that there are cubic graphs on 90 vertices having the same path layer matrix (Dobrynin, 1990). A new upper bound for the least order of cubic graphs with the same path layer matrix is presented. © 1993 John Wiley&Sons, Inc

ISSN:0364-9024    

DOI:10.1002/jgt.3190170102

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractLetp≥2be a fixed integer. LetGbe a simple and 2‐edge‐connected graph onnvertices, and letgbe the girth ofG.Ifd(u) +d(v) ≥ (2/(g − 2))((n/p) − 4 +g) holds wheneveruv∉E(G), and ifnis sufficiently large compared top, then eitherGhas a spanning eulerian subgraph orGcan be contracted to a graphG1of order at mostpwithout a spanning eulerian subgraph. Furthermore, we characterize the graphs that satisfy the conditions above such thatG1has orderpand does not have any spanning eulerian subgraph. © 1993 John W

ISSN:0364-9024    

DOI:10.1002/jgt.3190170103

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractWe give examples of edge‐chromatic critical graphsGof the following types: (i) of even order and having no 1‐factor, and (ii) of odd order and having a vertexvof minimum degree such thatG−vhas no 1‐factor. The first disproves a conjecture of S. Fiorini and R. J. Wilson, and the second answers a question of A. G. Chetwynd and H. P. Yap in the negative. © 1993 John Wiley&S

ISSN:0364-9024    

DOI:10.1002/jgt.3190170104

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractThis paper studies the relation between the connectivity and other parameters of a digraph (or graph), namely its ordern, minimum degree δ, maximum degree Δ, diameterD, and a new parameter lpi;,0≤ π ≤ δ − 2, related with the number of short paths (in the case of graphsl0= ⌊(g− 1)/2⌋ wheregstands for the girth). For instance, letG= (V,A) be a digraph onnvertices with maximum degree Δ and diameterD, so thatn≤n(Δ,D) = 1 + Δ + Δ2+ … + ΔD(Moore bound). As the main results it is shown that, if κ and λ denote respectively the connectivity and arc‐connectivity ofG,.Analogous results hold for graphs.

ISSN:0364-9024    

DOI:10.1002/jgt.3190170105

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractA graphGis domination perfect if for each induced subgraphHofG, γ(H) =i(H), where γ andiare a graph's domination number and independent domination number, respectively. Zverovich and Zverovich [3] offered a finite forbidden induced characterization of domination perfect graphs. This characterization is not correct, but the ideas in [3]can be used to weaken the known sufficient conditions for a graph to be domination perfect and to obtain short proofs of some results regarding domination perfect graphs. © 1993 John Wiley&Sons, I

ISSN:0364-9024    

DOI:10.1002/jgt.3190170106

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractWe describe a new class of graphs for which the stability number can be obtained in polynomial time. The algorithm is based on an iterative procedure that, at each step, builds from a graphGa new graphGlthat has fewer nodes and has the property that α(Gl) = α(G) − 1.This new class of graphs is different from the known classes for which the stability number can be computed in polynomial time. © 1993 John Wiley&Sons,

ISSN:0364-9024    

DOI:10.1002/jgt.3190170107

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractThe concept of the line graph can be generalized as follows. Thek‐line graphLk(G) of a graphGis defined as a graph whose vertices are the complete subgraphs onkvertices inG.Two distinct such complete subgraphs are adjacent inLk(G) if and only if they have inG k− 1 vertices in common. The concept of the total graph can be generalized similarly. Then the Perfect Graph Conjecture will be proved for 3‐line graphs and 3‐total graphs. Moreover, perfect 3‐line graphs are not contained in any of the known classes of perfect graphs. © 1993 John Wiley

ISSN:0364-9024    

DOI:10.1002/jgt.3190170108

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractIn this paper we give lower bounds and upper bounds for chromatic polynomials of simple undirected graphs onnvertices havingmedges and girth exceedingg© 1993 John Wiley&Sons, Inc

ISSN:0364-9024    

DOI:10.1002/jgt.3190170109

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractThek×ngrid graph is the productPk×Pnof a path of lengthk− 1 and a path of lengthn− 1. We prove here formulas found by E. O. Hare for the domination numbers ofP5×PnandP6×Pn. © 1993 John Wiley&S

ISSN:0364-9024    

DOI:10.1002/jgt.3190170110

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractLetex* (D;H) denote the maximum number of edges in a connected graph with maximum degreeDand no induced subgraph isomorphic toH.We prove that this is finite only whenHis a disjoint union of paths,m in which case we provide crude upper and lower bounds. WhenHis the four‐vertex pathP4, we prove that the complete bipartite graphKD,Dis the unique extremal graph. Furthermore, ifGis a connectedP4‐free graph with maximum degreeDand clique number ω, thenGhas at mostD2−D(ω − 2)/2 edges. © 1993 John Wiley

ISSN:0364-9024    

DOI:10.1002/jgt.3190170111

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY