摘要:

AbstractIt is proved that the maximal number of edges in a graph withn≧ 8 vertices that is not contractible toK8is 6n− 21, unless 5 dividesn, and the only graphs withn= 5mvertices and more than 6n− 21 edges that are not contractible toK8are theK5(2)‐cockades that have exactly 6n−

ISSN:0364-9024    

DOI:10.1002/jgt.3190180502

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

年代:1994

数据来源: WILEY

摘要:

AbstractWe construct 3‐regular (cubic) graphsGthat have a dominating cycleCsuch that no other cycleC1ofGsatisfiesV(C)⊆V(C1). By a similar construction we obtain loopless 4‐regular graphs having precisely one hamiltonian cycle. The basis for these constructions are considerations on the uniqueness of a cycle decomposition compatible with a given eulerian trail in some eulerian

ISSN:0364-9024    

DOI:10.1002/jgt.3190180503

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

年代:1994

数据来源: WILEY

摘要:

AbstractLetDbe an oriented graph of ordern≧ 9 and minimum degreen− 2. This paper proves thatDis pancyclic if for any two verticesuandv, eitheruv≅A(D), ordD+(u) +dD−(v

ISSN:0364-9024    

DOI:10.1002/jgt.3190180504

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

年代:1994

数据来源: WILEY

摘要:

AbstractWe say thatGis almost claw‐free if the vertices that are centers of induced claws (K1,3) inGare independent and their neighborhoods are 2‐dominated. Clearly, every claw‐free graph is almost claw‐free. It is shown that (i) every even connected almost claw‐free graph has a perfect matching and (ii) every nontrivial locally connectedK1,4‐free almost claw‐free graph is fully cyc

ISSN:0364-9024    

DOI:10.1002/jgt.3190180505

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

年代:1994

数据来源: WILEY

摘要:

AbstractAperfectdominatingset Sof a graph Γ is a set of vertices of Γ such that every vertex of Γ is either inSor is adjacent to exactly one vertex ofS.We show that a perfect dominating set of then‐cubeQninduces a subgraph ofQnwhose components are isomorphic to hypercubes. We conjecture that each of these hypercubes has the same dimension. We then prove that ifQris a component of the subgraph induced byS, thenn−r 1 or 3 (mod 6). A number of examples are given and connections with Steiner Systems and codes a

ISSN:0364-9024    

DOI:10.1002/jgt.3190180506

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

年代:1994

数据来源: WILEY

摘要:

AbstractLetG= (V, E) be a connected graph. A setD⊂Vis aset‐dominating set(sd‐set) if for every setT⊂V−D, there exists a nonempty setS⊂Dsuch that the subgraph 〈S∪T〉 induced byS∪Tis connected. The set‐domination number γs(G) ofGis the minimum cardinality of a sd‐set. In this paper we develop properties of this new parameter and relate it to some other kno

ISSN:0364-9024    

DOI:10.1002/jgt.3190180507

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

年代:1994

数据来源: WILEY

摘要:

AbstractIn this paper,k+ 1 real numbersc1,c2, ⃛,ck+1are found such that the following condition is sufficient for ak‐connected graph of ordernto be hamiltonian: for each independent vertex set ofk+ 1 vertices inG.where Si= {v ≅ V:|N(v) ∩ S| = i} for 0 ≦ i ≦k+ 1. Such a set ofk+ 1 numbers is called anHk‐sequence. A sufficient condition for the existence ofHk‐sequences is obtained that generalizes many known results involving sum of degrees, neighborhood unions, and/or neighborhoo

ISSN:0364-9024    

DOI:10.1002/jgt.3190180508

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

年代:1994

数据来源: WILEY

摘要:

AbstractGiven a digraphDon verticesv1,v2, ⃛,vn, we can associate a bipartite graphB(D)on verticess1,s2, ⃛,sn,t1,t2, ⃛,tn, wheresitjis an edge ofB(D)if (vi,vj) is an arc inD. LetOGdenote the set of all orientations on the (undirected) graphG. In this paper we will discuss properties of the setS(G) := {β1(B(D))) |D≅OG}, where β1is the edge independence number.In the first section we present some background and related concepts. We show that sets of the formS(G) are convex and that maxS(G) ≦ 2 minS(G). Furthermore, this completely characterizes such sets.In the second section we discuss some bounds on elements ofS(G) in terms of more familiar graphical parameters.The third section deals with extremal problems. We discuss bounds on elements ofS(G) if the order and size ofGare known, particularly whenGis bipartite. In this section we exhibit a relation between maxS(G) and the concept of graphical closure.In the fourth and final section we discuss the computational complexity of computing minS(G) and maxS(G). We show that the first problem is NP‐complete and that the latter

ISSN:0364-9024    

DOI:10.1002/jgt.3190180509

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

年代:1994

数据来源: WILEY

摘要:

AbstractWe show that the outvalency sequence of an infinite digraph is not, in general, reconstructible.

ISSN:0364-9024    

DOI:10.1002/jgt.3190180510

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

年代:1994

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190180501

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

年代:1994

数据来源: WILEY