摘要:

AbstractWe associate partitions of the edge‐set of a 4‐regular plane graph into 1‐factors or 2‐factors to certain 3‐valued vertex signatures in the spirit of the work by H. Grötzsch [1]. As a corollary we obtain a simple proof of a result of F. Jaeger and H. Shank [2]on the edge‐4‐colorability of 4‐regular plane graphs made up by the superposition of 4 families of disjoint simp

ISSN:0364-9024    

DOI:10.1002/jgt.3190140402

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe prove that ifTis any tree havingnedges (n≥ 1), then then‐cubeQncan be decomposed into 2n‐1edge‐disjoint induced subgraphs, each of which is isomorphic toT.We use this statement to obtain two results concerning decompositions ofQninto subgraphs isomorphic to members of a specified family o

ISSN:0364-9024    

DOI:10.1002/jgt.3190140403

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

年代:1990

数据来源: WILEY

摘要:

AbstractNew characterizations of triangulated and cotriangulated graphs are presented. Cotriangulated graphs form a natural subclass of the class of strongly perfect graphs, and they are also characterized in terms of the shellability of some associated collection of sets. Finally, the notion of stability function of a graph is introduced, and it is proved that a graph is triangulated if and only if the polynomial representing its stability function has all its coefficients equal to 0, +1 or −

ISSN:0364-9024    

DOI:10.1002/jgt.3190140404

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

年代:1990

数据来源: WILEY

摘要:

AbstractA picture is a simple graph together with an edge‐coloring, such that each vertex is incident with exactly one edge of each color. An automorphism of a picture is a graph automorphism that preserves the colors of the edges. We show that every group is isomorphic to the full automorphism group of a picture, and prove that a group is isomorphic to a vertex‐transitive subgroup of the automorphism group of a picture if and only if it can be generated by involuti

ISSN:0364-9024    

DOI:10.1002/jgt.3190140405

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe study classes of finite, simple, undirected graphs that are (1) lower ideals (or hereditary) in the partial order of graphs by the induced subgraph relation ≤i, and (2) well‐quasi‐ordered (WQO) by this relation. The main result shows that the class of cographs (P4‐free graphs) is WQO by ≤i, and that this is the unique maximal lower ideal with one forbidden subgraph that is WQO. This is a consequence of the famous Kruskal theorem. Modifying our idea we can prove thatP4‐reducible graphs build a WQO class. Other examples of lower ideals WQO by ≤ia

ISSN:0364-9024    

DOI:10.1002/jgt.3190140406

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

年代:1990

数据来源: WILEY

摘要:

AbstractThe irredundant Ramsey numbers(m, n)is the smallest p such that in every two‐coloring of the edges ofKpusing colors red (R) and blue (B), either the blue graph contains anm‐element irredundant set or the red graph contains ann‐element irredundant set. We develop techniques to obtain upper bounds for irredundant Ramsey numbers of the forms(3,n) and prove that 18 ≤s(3,

ISSN:0364-9024    

DOI:10.1002/jgt.3190140407

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe construct graphs that contain all bounded‐degree trees onnvertices as induced subgraphs and have onlycnedges for some constantcdepending only on the maximum degree. In general, we consider the problem of determining the graphs, so‐called universal graphs (or induced‐universal graphs), with as few vertices and edges as possible having the property that all graphs in a specified family are contained as subgraphs (or induced subgraphs). We obtain bounds for the size of universal and induced‐universal graphs for many classes of graphs such as trees and planar graphs. These bounds are obtained by establishing relationships between the universal graphs and the induced‐univers

ISSN:0364-9024    

DOI:10.1002/jgt.3190140408

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

年代:1990

数据来源: WILEY

摘要:

AbstractIn a connected graph define the k‐center as the set of vertices whose distance from any other vertex is at mostk.We say that a vertex setSd‐dominatesGif for every vertex x there is a y ∈Swhose distance fromxis at mostd.Call a graphPt‐free if it does not contain a path ontvertices as an induced subgraph. We prove that a connected graph isP2k‐1‐free (P2k‐free) if and only if each of its connected induced subgraphsHsatisfy the following property: Thek‐center ofH(k‐ 1)‐dominates ((k‐ 2)‐dominates)H.Moreover, we show that the subgraph induced by the (t‐ 3)‐center in anyPt‐free connected graph is again connected

ISSN:0364-9024    

DOI:10.1002/jgt.3190140409

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

年代:1990

数据来源: WILEY

摘要:

AbstractAn edgeeof a 3‐connected graphGis said to beremovableifG‐eis a subdivision of a 3‐connected graph. Ifeis not removable, theneis said to benonremovable.In this paper, we study the distribution of removable edges in 3‐connected graphs and prove that a 3‐connected graph of ordern≥ 5 has at most [(4n— 5)/3] nonre

ISSN:0364-9024    

DOI:10.1002/jgt.3190140410

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe show that a 3‐edge‐connected graph embedded in a surface of Euler characteristic χ has at most 3 – 3χ singular edges, except in the projective plane, where it has at most one singular edge, and the sphere, where it has none. This bound is best possible for all s

ISSN:0364-9024    

DOI:10.1002/jgt.3190140411

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

年代:1990

数据来源: WILEY