ISSN:0364-9024    

DOI:10.1002/jgt.3190050402

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

年代:1981

数据来源: WILEY

摘要:

AbstractWe show that everyk‐connected graph with no 3‐cycle contains an edge whose contraction results in ak‐connected graph and use this to prove that every (k+ 3)‐connected graph contains a cycle whose deletion results in ak‐connected graph. This settles a problem of

ISSN:0364-9024    

DOI:10.1002/jgt.3190050403

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

年代:1981

数据来源: WILEY

摘要:

AbstractCurrent graphs and a theorem of White are used to show the existence of almost complete regular bipartite graphs with quadrilateral embeddings conjectured by Pisanski. Decompositions ofKnandKn, ninto graphs with quadrilateral embeddings are discussed, and some thickness results are obtained. Some new genus results are also obtained.

ISSN:0364-9024    

DOI:10.1002/jgt.3190050404

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

年代:1981

数据来源: WILEY

摘要:

AbstractFor an arbitrary treeTof ordermand an arbitrary positive integern, Chvátal proved that the Ramsey numberr(T, Kn)= 1 + (m− 1) (n− 1). for graphsG, G1, andG2, we say thatGarrowsG1andG2, writtenG→ (G1,G2), if for every factorizationG=R⊕B, eitherG1is a subgraph ofRorG2is a subgraph ofB. it is shown that (i) for eachl ≥ 2, K1+ (m−1)(n−1)−E(K1)→ (T, Kn)form ≥ 2/− 1 andn≥ 2; (ii)K1+,(m −1)(n −1) −E(H)→ (T, Kn), whereHis any tree of orderm− 1,m≥ 3 andn≥ 2. It is further shown that result (i) is sharp with respect to the inequalitym≥2/− 1; in particular, examples are given to show thatK1 + (2l−3)(n−1)E(K1)↛ (P21−2, Kn)for alln≥ 2, whereP21−2denotes the path of order21− 2. Also result (ii) is sharp with respect to the order ofH; examples aregiven to show thatK1+(m−1)(n

ISSN:0364-9024    

DOI:10.1002/jgt.3190050405

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

年代:1981

数据来源: WILEY

摘要:

AbstractA graphGhas propertyA(m, n, k)if for any sequence ofm+ndistinct points ofG, there are at leastkother points, each of which is adjacent to the firstmpoints of the sequence but not adjacent to any of the latternpoints. the minimum order among all graphs with propertyA(m, n, k)is denoteda(m, n, k). Bounds are given on the numbersa(m, n, k)and some exact results are indicated.

ISSN:0364-9024    

DOI:10.1002/jgt.3190050406

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

年代:1981

数据来源: WILEY

摘要:

AbstractThe concept of the binding number of a graph was introduced by Woodall in 1973. in this paper we characterize the setFnof all pairs (a, b) of integers such that there is a graphGwithnvertices and binding numbera/bthat has a realizing set ofbvertices.

ISSN:0364-9024    

DOI:10.1002/jgt.3190050407

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

年代:1981

数据来源: WILEY

摘要:

AbstractGeneralized line graphs extend the ideas of both line graphs and cocktail party graphs. They were originally motivated by spectral considerations. in this paper several (nonspectral) classical theorems about line graphs are extended to generalized line graphs, including the derivation and construction of the 31 minimal nongeneralized line graphs, a Krausz‐type covering characterization, and Whitney‐type theorems on isomorphisms and automorphi

ISSN:0364-9024    

DOI:10.1002/jgt.3190050408

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

年代:1981

数据来源: WILEY

摘要:

AbstractThe possible classes of balanced circles of a signed graph are characterized in two ways.

ISSN:0364-9024    

DOI:10.1002/jgt.3190050409

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

年代:1981

数据来源: WILEY

摘要:

AbstractFor bipartite graphs the property of being Hamilton laceable is analogous to the property of being Hamilton connected for simple graphs. in this paper it is proven that all of the graphs obtained by deleting fewer thanm− 1 edges from either of the complete bipartite graphsKm, morKm, m+1are Hamilton laceable. It is also proven that the deletion ofm− 1 edges results in a non‐Hamiltonlaceable graph if and only if the graph is either the complement of the starK1,m−1inKm, morKm, m+1or else the complement inK3,3of a pair of nonadjacen

ISSN:0364-9024    

DOI:10.1002/jgt.3190050410

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

年代:1981

数据来源: WILEY

摘要:

AbstractA graph is called locally homogeneous if the subgraphs induced at any two points are isomorphic. in this Note we give a method for constructing locally homogeneous graphs from groups. the graphs constructable in this way are exactly the locally homogeneous graphs with a point symmetric universal cover. As an example we characterize the graphs that are locallyn‐cycle

ISSN:0364-9024    

DOI:10.1002/jgt.3190050411

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

年代:1981

数据来源: WILEY