摘要:

AbstractIn a graphG, a setXis called a stable set if any two vertices ofXare nonadjacent. A setXis called a dominating set if every vertex ofV – Xis joined to at least one vertex ofX.A setXis called an irredundant set if every vertex ofX, not isolated inX, has at least one proper neighbor, that is a vertex ofV – Xjoined to it but to no other vertex ofX.Let α′ and α, γ, and Γ,irandIR, denote respectively the minimum and maximum cardinalities of a maximal stable set, a minimal dominating set, and a maximal irredundant set. It is known thatir⩽ γ ⩽ α′ ⩽ α ⩽ Γ ⩽IRand that ifGdoes not contain any induced subgraph isomorphic toK1,3, then γ = α′. Here we prove that ifGcontains no induced subgraph isomorphic toK1,3or to the graphHof figure 1, then ir = γ = α′. We prove also that ifGcontains no induced subgraph isomorphic toK1,3, toH, or to the graphhof figure 3, then Γ =IR.Finally, we improve a result of Bollobas and Cockayne about sufficient conditions for γ

ISSN:0364-9024    

DOI:10.1002/jgt.3190100402

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

年代:1986

数据来源: WILEY

摘要:

AbstractA simple graphG(X,E) is factor‐critical if the induced subgraph 〈X–x〉 admits a perfect matching for every vertexxofG.It is equimatchable if every maximal matching ofGis maximum. The equimatchable non‐factor‐critical graphs have been studied by Lesk, Plummer, and Pulleyblank. In this paper, we study the equimatchable factor‐critical graphs; in particular we show that if such a graph is two‐connected, it

ISSN:0364-9024    

DOI:10.1002/jgt.3190100403

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

年代:1986

数据来源: WILEY

摘要:

AbstractC. Thomassen extended Tutte's theorem on cycles in planar graphs in the paper “A Theorem on Paths in Planar Graphs”. This note corrects a flaw in his pr

ISSN:0364-9024    

DOI:10.1002/jgt.3190100404

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

年代:1986

数据来源: WILEY

摘要:

AbstractA finite simplicial complex isorderableif its simplices are the chains of a poset. For each closed surface an orderable triangulation is given that is minimal with respect to the number of vertices. The construction of minimal ordered triangulations implies that for each surfaceSthe minimal number of vertices of a bipartite graph, which has a quadrilateral embedding intoS, is equal tob(S)= ⌈4 + (16 – 8χ)1/2⌉, where χ is the Euler characteris

ISSN:0364-9024    

DOI:10.1002/jgt.3190100405

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

年代:1986

数据来源: WILEY

摘要:

AbstractA graphLis called a link graph if there is a graphGsuch that for each vertex ofGits neighbors induce a subgraph isomorphic toL.Such aGis said to have constant linkL.We prove that for any finite group Γ and any disconnected link graphLwith at least three vertices there are infinitely many connected graphsGwith constant linkLand AutG⋍ Γ. We look at the analogous problem for connected link graphs, namely, link graphs that are paths or have disconnected complements. Furthermore we prove that forn, r≥ 2, but notn= 2 =r, any finite group can be represented by infinitely many connectedr‐uniform,n‐regular hypergraphs of arbitrarily la

ISSN:0364-9024    

DOI:10.1002/jgt.3190100406

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

年代:1986

数据来源: WILEY

摘要:

AbstractLetGbe a triangle‐free, loopless graph with maximum degree three. We display a polynomial algorithm which returns a bipartite subgraph ofGcontaining at least ⅘ of the edges ofG.Furthermore, we characterize the dodecahedron and the Petersen graph as the only 3‐regular, triangle‐free, loopless, connected graphs for which no bipartite subgraph has more than this pro

ISSN:0364-9024    

DOI:10.1002/jgt.3190100407

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

年代:1986

数据来源: WILEY

摘要:

AbstractThe linear arboricity of the graphGis the minimum number of linear forests whose union isG.In the paper exact values and bounds of linear arboricity for some additional classes of graphs are determined.

ISSN:0364-9024    

DOI:10.1002/jgt.3190100408

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

年代:1986

数据来源: WILEY

摘要:

AbstractA fold is a sequence of simple folds (elementary homomorphisms in which the identified vertices are both adjacent to a common vertex). It was shown in (C. R. Cook and A. B. Evans, Graph folding.Proceedings of the South Eastern Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, 1979, pp. 305–314) that all connectedn‐chromatic graphs can be folded ontoKn. A connected n‐chromatic graph is called absolutelyn‐chromatic if it can only be folded ontoKmwhenm = n.Some classes of absolutely n‐chromatic graphs were given in Cook and Evans. In this paper, we classify the absolutely 3‐chrom

ISSN:0364-9024    

DOI:10.1002/jgt.3190100409

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

年代:1986

数据来源: WILEY

摘要:

AbstractLetK 2n+1(r)denote the complete graphK2n+1with each edge replicatedrtimes and let χ′(G) denote the chromatic index of a multigraphG.A multigraphGiscriticalif χ′(G)>χ′(G/e) for each edgeeofG.LetSbe a set ofsn– 1 edges ofK 2n+1(r). We show that, for 0

ISSN:0364-9024    

DOI:10.1002/jgt.3190100410

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

年代:1986

数据来源: WILEY

摘要:

AbstractIn a recent paper, Carsten Thomassen [Carsten Thomassen, Planarity and duality of finite and infinite graphs.J. Combinatorial Theory Ser. B29 (1980) 244–271] has shown that a number of criteria for the planarity of a graph can be reduced to that of Kuratowski. Here we present another criterion which, as well, is easily proved via Kuratowski's. The criterion is based on the observation that the imbedding of a graph in a plane imposes a cyclic ordering, say clockwise, on the edges incident with each vertex, and that these cyclic orderings are relate

ISSN:0364-9024    

DOI:10.1002/jgt.3190100411

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

年代:1986

数据来源: WILEY