摘要:

AbstractThe path layer matrix (or path degree sequence) of a graphGcontains quantitative information about all paths inG.Elements (i,j) in this matrix is the number of simple paths inGhaving initial vertexv, and lengthj.For everyr≥ 3, pairs of nonisomorphicr‐regular graphs having the same path layer matrix are presen

ISSN:0364-9024    

DOI:10.1002/jgt.3190140202

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

年代:1990

数据来源: WILEY

摘要:

AbstractTheally‐reconstruction numberof a graphG, ally‐rn(G), is the minimum number of vertex‐deleted subgraphs required in order to identifyGup to isomorphism. In this paper, we show that ally‐rn(T) = 3 for any treeTwith five or more v

ISSN:0364-9024    

DOI:10.1002/jgt.3190140203

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe obtain lower bounds on the size of a maximum matching in a graph satisfying the condition |N(X)| ≥sfor every independent setXofmvertices, thus generalizing results of Faudree, Gould, Jacobson, and Schelp for the casem=

ISSN:0364-9024    

DOI:10.1002/jgt.3190140204

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

年代:1990

数据来源: WILEY

摘要:

AbstractIf a graphGonnvertices contains a Hamiltonian path, thenGis reconstructible from its edge‐deleted subgraphs fornsufficiently larg

ISSN:0364-9024    

DOI:10.1002/jgt.3190140205

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

年代:1990

数据来源: WILEY

摘要:

AbstractLower bounds on the size of a maximum bipartite subgraph of a triangle‐freer‐regular graph are presen

ISSN:0364-9024    

DOI:10.1002/jgt.3190140206

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

年代:1990

数据来源: WILEY

摘要:

AbstractLetGbe a graph and letk′(G) be the edge‐connectivity ofG. ThestrengthofG, denoted by k̄′(G), is the maximum value ofk′(H), whereHruns over all subgraphs ofG. A simple graphGis called k‐maximalif k̄′(G) ≤kbut for any edgee∈E(Gc), k̄′(G+e) ≥k+ 1. LetGbe ak‐maximal graph of ordern. In [3], Mader proved |E(G)| ≤ (n‐k)k+ ( 2k). In this note, we shall show (n‐ 1)k‐ ( 2k) In⌊n/k+ 2)⌋ ≤ |E(G|, and characterize the extremal graphs. We shall also give

ISSN:0364-9024    

DOI:10.1002/jgt.3190140207

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

年代:1990

数据来源: WILEY

摘要:

AbstractAcoveringis a graph map ϕ:G→Hthat is an isomorphism when restricted to the star of any vertex ofG. IfHis connected then |ϕ−1(v)| is constant. This constant is called thefold number. In this paper we prove that ifGis a planar graph that covers a nonplanarH, then the fold number must be

ISSN:0364-9024    

DOI:10.1002/jgt.3190140208

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

年代:1990

数据来源: WILEY

摘要:

AbstractIn this paper we show that every connected, 3‐γ‐critical graph on more than 6 vertices has a Hamiltonian

ISSN:0364-9024    

DOI:10.1002/jgt.3190140209

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

年代:1990

数据来源: WILEY

摘要:

AbstractLet\documentclass{article}\pagestyle{empty}\begin{document}$ \mathop {\rm D}\limits^ \to $\end{document}(n, M) denote a digraph chosen at random from the family of all digraphs onnvertices withMarcs. We shall prove that ifM/n≤c1 the largest component of\documentclass{article}\pagestyle{empty}\begin{document}$ \mathop {\rm D}\limits^ \to $\end{document}(n, M) is of the ordernwith probab

ISSN:0364-9024    

DOI:10.1002/jgt.3190140210

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

年代:1990

数据来源: WILEY

摘要:

AbstractA graph is called Class 1 if the chromatic index equals the maximum degree. We prove sufficient conditions for simple graphs to be Class 1. Using these conditions we improve results on some edge‐coloring theorems of Chetwynd and Hilton. We also improve a theorem concerning the 1‐factorization of regular graphs of high deg

ISSN:0364-9024    

DOI:10.1002/jgt.3190140211

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

年代:1990

数据来源: WILEY