ISSN:0364-9024    

DOI:10.1002/jgt.3190060202

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

年代:1982

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190060203

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

年代:1982

数据来源: WILEY

摘要:

AbstractIn this paper are investigated maximum bipartite subgraphs of graphs, i.e., bipartite subgraphs with a maximum number of edges. Such subgraphs are characterized and a criterion is given for a subgraph to be a unique maximum bipartite subgraph of a given graph. In particular maximum bipartite subgraphs of cubic graphs are investigated. It is shown that cubic graphs can be built up from five building stones (called elementary paths). Finally the investigation of a special class of cubic graphs yields a theorem which characterizes the Petersen graph and the dodecahedron graph by means of their maximum bipartite subgraphs.

ISSN:0364-9024    

DOI:10.1002/jgt.3190060204

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

年代:1982

数据来源: WILEY

摘要:

AbstractA cubic triangle‐free graph has a bipartite subgraph with at least 4/5 of the original edges. Examples show that this is a best possible resul

ISSN:0364-9024    

DOI:10.1002/jgt.3190060205

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

年代:1982

数据来源: WILEY

摘要:

AbstractA lower bound is established on the number of edges in a maximumk‐colorable subgraph of a loopless graphG. For the special case of 3‐regular graphs, lower bounds are also determined on the maximum number of edges in a bipartite subgraph whose color classes are of equal s

ISSN:0364-9024    

DOI:10.1002/jgt.3190060206

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

年代:1982

数据来源: WILEY

摘要:

AbstractLett(n) denote the greatest number of arcs in a diagraph of ordersnwhich does not contain any antidrected cycles. We show that [16/5(n− 1)] ≤t(n) ≤ 1/2 (n− 1) for n ≥ 5. Lettr(n) denote the corresponding quantity forr‐colorable digraphs. We show that [16/5(n− 1)] ≤t5(n) ≤t6(n) ≤ 10/3(n− 1) forn≥ 5 and that

ISSN:0364-9024    

DOI:10.1002/jgt.3190060207

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

年代:1982

数据来源: WILEY

摘要:

AbstractIt is shown that, for all sufficiently largek, the complete graphKncan be decomposed intokfactors of diameter 2 if and only ifn≥ 6

ISSN:0364-9024    

DOI:10.1002/jgt.3190060208

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

年代:1982

数据来源: WILEY

摘要:

AbstractThis paper concerns the degree sequenced1≥d2≥ … ≥dnof a randomly labeled graph of ordernin which the probability of an edge isp(n)≦ 1/2. Among other results the following questions are answered. What are the values ofp(n) for whichd1, the maximum degree, is the same for almost every graph? For what values ofp(n) is it true thatd2>d2for almost every graph, that is, there is a unique vertex of maximum degree? The answers are (essentially)p(n) = o(logn/n/n) andp(n)n/logn→ ∞. Also included is a detailed study of the distribution of degrees when 0

ISSN:0364-9024    

DOI:10.1002/jgt.3190060209

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

年代:1982

数据来源: WILEY

摘要:

AbstractA new class of geodetic blocks is constructed and it is shown how these are derived from Plesnik's geodetic homeomorphs of complete graphs.

ISSN:0364-9024    

DOI:10.1002/jgt.3190060210

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

年代:1982

数据来源: WILEY

摘要:

AbstractLetr≧ 3 be an integer. It is shown that there exists ε= ε(r), 0<ε0 such that for alln≧N(ifris even) or for all evenn≧N(ifris odd), there is anr‐connected regular graph of valencyron exactlynvertices whose longest cycles have fewer than

ISSN:0364-9024    

DOI:10.1002/jgt.3190060211

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

年代:1982

数据来源: WILEY