摘要:

AbstractLet γ(G) andi(G) be the domination number and independent domination number of a graphG, respectively. Sumner and Moore [8] define a graph G to be domination perfect if γ(H) =i(H), for every induced subgraphHofG.In this article, we give a finite forbidden induced subgraph characterization of domination perfect graphs.Bollobás and Cockayne [4] proved an inequality relating γ(G) andi(G) for the class of K1,k‐free graphs. It is shown that the same inequality holds for a wider class of g

ISSN:0364-9024    

DOI:10.1002/jgt.3190150202

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

年代:1991

数据来源: WILEY

摘要:

AbstractWang and Williams defined athreshold assignmentfor a graphGas an assignment of a non‐negative weight to each vertex and edge ofG, and a thresholdt, such that a setSof vertices is stable if and only if the total weight of the subgraph induced bySdoes not exceedt‐ 1. This is always possible with zero vertex‐weights, unit edge‐weights, andt= 1. By definition, athreshold graphis a graph having a threshold assignment with zero edge‐weights. Thethreshold weightofGis the minimum total edgeweight of a threshold assignment ofG.A graphG= (V,E) is calledheavyif its threshold weight is |E|. A cliqueCofGis calledbigif |E(C)|>|E(G‐C)|. Wang and Williams showed that graphs with a big clique are not heavy, and conjectured the converse. They verified the conjecture for triangle‐free graphs. We disprove the conjecture in general, but prove it for p

ISSN:0364-9024    

DOI:10.1002/jgt.3190150203

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

年代:1991

数据来源: WILEY

摘要:

AbstractThis is intended as a survey article covering recent developments in the area of hamiltonian graphs, that is, graphs containing a spanning cycle. This article also contains some material on related topics such as traceable, hamiltonian‐connected and pancyclic graphs and digraphs, as well as an extensive bibliography of papers in the are

ISSN:0364-9024    

DOI:10.1002/jgt.3190150204

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

年代:1991

数据来源: WILEY

摘要:

AbstractBeyond the obvious organization of all the orientable imbeddings of a graph according to the genus of the imbedding surface, there are several seemingly natural ways to ascribe proximity of imbeddings. One of these is to stipulate that two imbeddings are adjacent if one imbedding can be obtained from the other by moving one end of an edge in its rotation. If one associates “altitude” with genus, then one might hope to construct algorithms for minimum genus and maximum genus by descent and ascent, respectively. This investigation of the structure of the system of orientable graph imbeddings reveals that although there may occur arbitrarily deep traps among the local minima, there cannot exist any strict local maxima. These new discoveries seem consistent with a known contrast in the computational complexity of the maximum genus and minimum genus problems. That is, whereas Furst, Gross, and McGeoch have devised a polynomial‐time algorithm to find the maximum genus of an arbitrary graph, Thomassen has proved that the problem of finding the minimum genus is NP‐c

ISSN:0364-9024    

DOI:10.1002/jgt.3190150205

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

年代:1991

数据来源: WILEY

摘要:

AbstractWe introduce a large class of tournament properties, all of which are shared by almost all random tournaments. These properties, which we term “quasi‐random,” have the property that tournaments possessing any one of the properties must of necessity possess them all. In contrast to random tournaments, however, it is often very easy to verify that a particular family of tournaments satisfies one of the quasi‐random properties, thereby giving explicit tournaments with “random‐like” behavior. This paper continues an approach initiated in several earlier papers of the authors where analogous results for graphs (with R.M. Wilson) and hypergrap

ISSN:0364-9024    

DOI:10.1002/jgt.3190150206

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

年代:1991

数据来源: WILEY

摘要:

AbstractA graph is said to beprojective‐planarif it is nonplanar and is embeddable in a projective plane. In this paper we show that the numbers of projectiveplanar embeddings (up to equivalence) of all 5‐connected graphs have an upper boundc(

ISSN:0364-9024    

DOI:10.1002/jgt.3190150207

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

年代:1991

数据来源: WILEY

摘要:

AbstractA subset of vertices is a maximum independent set if no two of the vertices are joined by an edge and the subset has maximum cardinality. in this paper we answer a question posed by Herb Wilf. We show that the greatest number of maximum independent sets for a tree ofnvertices isWe give the families of trees on which these maxima are achieved.Proving which trees are extremal depends upon the structure of maximum independent sets in trees. This structure is described in terms of adjacency rules between three types of vertices, those which are in all, no, or some maximum independent sets. We show that vertices that are in some but not all maximum independent sets of the tree are joined in pairs by the α‐critical edges (edges whose removal increases the size of a maximum independent set). The number of maximum independent sets is shown to depend on the structure within the tree of the α‐critical

ISSN:0364-9024    

DOI:10.1002/jgt.3190150208

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

年代:1991

数据来源: WILEY

摘要:

AbstractSeven criteria for integer sequences being graphic are listed. Being graphic means that there is a simple graph with the given integer sequence as degree sequence. One of the criteria leads to a new and constructive proof of the well‐known criterion of Erdös‐Ga

ISSN:0364-9024    

DOI:10.1002/jgt.3190150209

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

年代:1991

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190150201

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

年代:1991

数据来源: WILEY