摘要:

AbstractLetB(G)be the edge set of a bipartite subgraph of a graphGwith the maximum number of edges. Letbk= inf{|B(G)|/|E(G)‖Gis a cubic graph with girth at leastk}. We will prove that limk → ∞bk

ISSN:0364-9024    

DOI:10.1002/jgt.3190140602

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

年代:1990

数据来源: WILEY

摘要:

AbstractAn edge of a 3‐connected graph is said to becontractibleif its contraction results in a 3‐connected graph. In this paper, a covering of contractible edges is studied. We give an alternative proof to the result of Ota and Saito (Scientia(A)2(1988) 101–105) that the set of contractible edges in a 3‐connected graph cannot be covered by two vertices, and extended this result to a three‐vertex covering. We also study the existence of a contractible edge whose contraction preserves a specified cycle, and show that a non‐hamiltonian 3‐connected graph has a contractible edge whose contraction preserves the

ISSN:0364-9024    

DOI:10.1002/jgt.3190140603

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe prove in this paper that every simple graphGadmits a perfect path double cover (PPDC), i.e., a set of paths ofGsuch that each edge ofGbelongs to exactly two of the paths and each vertex ofGis an end of exactly two of the paths, where a path of length zero is considered to have (identical) ends. This was conjectured by A. Bondy in 1988.

ISSN:0364-9024    

DOI:10.1002/jgt.3190140604

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

年代:1990

数据来源: WILEY

摘要:

AbstractLetP(x,y,n) be a real polynomial and let {Gn} be a family of graphs, where the set of vertices ofGnis {1,2,…,n} and for 1 ≤i0. Motivated by a question of Babai, we show that there is a positive constantcdepending only onPsuch that eitherGnor its complementGncontainsacomplete subgraph on at leastc21/2√lognvertices. Similarly, eitherGnorGncontains a complete bipartite subgraph with at leastcn1/2vertices in each color class. Similar results are proved for graphs defined by real polynomials in a more general way, showing that such graphs satisfy much stronger Ramsey bounds than do random graphs. This may partially explain the difficulties in finding an explicit construction for good Ramsey

ISSN:0364-9024    

DOI:10.1002/jgt.3190140605

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe characterize the family of hamiltonian tournaments with the least number of 3‐cycles, studying their structure and their score sequence. Furthermore, we obtain the number of nonisomorphic tournaments of this famil

ISSN:0364-9024    

DOI:10.1002/jgt.3190140606

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

年代:1990

数据来源: WILEY

摘要:

AbstractSuppose thatGis a finite simple graph with |V(G)| = 2n(n≠ 3). a partition (X,Y) ofV(G) is balanced if(i) |X| = |Y| =n,(ii) δ(X) ≥ 1, δ(Y) ≥ 1.Where δ(X) is the minimum degree of the induced subgraph 〈X〉 with vertex setX.We prove that if |E(G)| ≥ (n2+n+ 2)/2 andGis connected, thenGcontains a balanced partition. The r

ISSN:0364-9024    

DOI:10.1002/jgt.3190140607

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

年代:1990

数据来源: WILEY

摘要:

AbstractFor its implications in the design of interconnection networks, it is interesting to find(a) (di)graphs with given maximum (out‐)degreedand diameterDthat have large order;(b) (di)graphs of given order and maximum (out‐)degreedthat have small diameter.(Di)graphs of either type are often called dense.This paper considers the case of bipartite digraphs. For problem (a) it is shown that a Moore‐like bound on the order of such digraphs can be (and in fact is) attained only whenD≤ 4. ForD>4 a construction is presented that yields a family of bipartite digraphs with order larger than (d4— 1)/d4times the above‐mentioned bound. For problem (b) an appropriate lower bound is derived and a construction is presented that provides bipartite digraphs of any (even) order whose diameter does not exceed this lower bound in mo

ISSN:0364-9024    

DOI:10.1002/jgt.3190140608

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

年代:1990

数据来源: WILEY

摘要:

AbstractThe vertices of each plane triangulation without loops and multiple edges may be colored with 11 colors so that for every two adjacent triangles [xyz] and [wxy], the verticesx,y,w,zare colored pairwise differently.

ISSN:0364-9024    

DOI:10.1002/jgt.3190140609

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe prove two conjectures of Broersma and Hoede about path graphs of trees and unicyclic graphs.

ISSN:0364-9024    

DOI:10.1002/jgt.3190140610

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

年代:1990

数据来源: WILEY

摘要:

AbstractTwo source‐sink (directed) networks are calledpath‐isomorphicif there exists a bijection π between their arc sets that preserves (simple) source‐sink directed paths. Although path‐isomorphic networks need not be isomorphic (they need not even have the same number of nodes), we show that several properties are preserved. For example, supposeNandN′are path‐isomorphic. Then,Nis acyclic if and only ifN′is acyclic.Bis the arc set of block ofNif and only if π(B) is the arc set of a block ofN′. Also,Dis the arc set of a dicomponent ofNif and only if π(D) is the arc set of a dicomponent ofN′.In addition, we prove a dipath version of Whitney's well‐known 2‐isomorphism theorem for a special class of networks, which inclu

ISSN:0364-9024    

DOI:10.1002/jgt.3190140611

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

年代:1990

数据来源: WILEY