摘要:

AbstractSuppose thatG, Hare infinite graphs and there is a bijection Ψ; V(G) Ψ V(H) such thatG‐ ξ ≅ H ‐ Ψ(ξ) for every ξ ∼V(G). LetJbe a finite graph and /(π) be a cardinal number for each π ≅V(J). Suppose also that either /(π) is infinite for every π ≅V(J) orJhas a connected subgraphCsuch that /(π) is finite for every π ≅V(C) and every vertex inV(J)/V(C)is adjacent to a vertex ofC.Let(J, I, G)be the set of those subgraphs ofGthat are isomorphic toJunder isomorphisms that map each vertex π ofJto a vertex whose valency inGis /(π). We prove that the sets(J, I, G), m(J, I, H)have the same cardinality and include equal numbers of induced s

ISSN:0364-9024    

DOI:10.1002/jgt.3190180202

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

年代:1994

数据来源: WILEY

摘要:

AbstractA class of graphs χ is said to be χ‐bounded, with χ‐binding functionf, if for allGϵ Γ, χ (G) ≦ f (ω(G)), where χ(G) is the chromatic number ofGand ω(G) is the clique number ofG. It has been conjectured that for every treeT, the class of graphs that do not induceTis χ‐bounded. We show that this is true in the case whereTis a t

ISSN:0364-9024    

DOI:10.1002/jgt.3190180203

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

年代:1994

数据来源: WILEY

摘要:

AbstractLetGbe a bridgeless cubic graph. We prove that the edges ofGcan be covered by circuits whose total length is at most (44/27) |E(G)|, and if Tutte's 3‐flow Conjecture is true, at most (92/57) |E(G)

ISSN:0364-9024    

DOI:10.1002/jgt.3190180204

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

年代:1994

数据来源: WILEY

摘要:

AbstractAs a consequence of our main result, a theorem of Schrijver and Seymour that determines the zero sum Ramsey numbers for the family of allr‐hypertrees onmedges and a theorem of Bialostocki and Dierker that determines the zero sum Ramsey numbers forr‐hypermatchings are combined into a single theorem. Another consequence is the determination of zero sum Ramsey numbers of multiple copies of some small gra

ISSN:0364-9024    

DOI:10.1002/jgt.3190180205

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

年代:1994

数据来源: WILEY

摘要:

AbstractThe concept of a (1, 2)‐eulerian weight was introduced and studied in several papers recently by Seymour, Alspach, Goddyn, and Zhang. In this paper, we proved that ifGis a 2‐connected simple graph of ordern (n≧ 7) andwis a smallest (1, 2)‐eulerian weight of graphG, then |Ew=even|n‐ 4, except for a family of graphs. Consequently, ifGadmits a nowhere‐zero 4‐flow and is of order at least 7, except for a family of graphs, the total length of a shortest cycle covering is at most |V(G)| + |E(G)|‐ 4. This result generalizes some previous results due to Bermond, Jackson, Ja

ISSN:0364-9024    

DOI:10.1002/jgt.3190180206

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

年代:1994

数据来源: WILEY

摘要:

AbstractA path onnvertices is denoted byPn. For any graphH, the number of isolated vertices ofHis denoted byi(H). LetGbe a graph. A spanning subgraphFofGis called a {P3,P4,P5}‐factor ofGif every component ofFis one ofP3,P4, andP5. In this paper, we prove that a bipartite graphGhas a {P3,P4,P5}‐factor if and only ifi(G − S − M)≦ 2|S| + |M| for allS⊆V(G)and indepe

ISSN:0364-9024    

DOI:10.1002/jgt.3190180207

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

年代:1994

数据来源: WILEY

摘要:

AbstractGreene's Theorem states that the maximum cardinality of an optimalk‐path in a poset is equal to the minimumk‐norm of ak‐optimal coloring. This result was extended to all acyclic digraphs, and is conjectured to hold for general digraphs. We prove the result for general digraphs in which an optimalk‐path contains a path of cardinality one. This implies the validity of the conjecture for all bipartite digraphs. We also extend Greene's Theorem to all split

ISSN:0364-9024    

DOI:10.1002/jgt.3190180208

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

年代:1994

数据来源: WILEY

摘要:

AbstractIn this paper the conjecture on thekth upper multiexponent of primitive matrices proposed by R.A. Brualdi and Liu are completely proved.

ISSN:0364-9024    

DOI:10.1002/jgt.3190180209

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

年代:1994

数据来源: WILEY

摘要:

AbstractIt is well known that the smallest eigenvalue of the adjacency matrix of a connectedd‐regular graph is at least −dand is strictly greater than −dif the graph is not bipartite. More generally, for any connected graphG = (V, E), consider the matrixQ = D + AwhereDis the diagonal matrix of degrees in the graphGandAis the adjacency matrix ofG. ThenQis positive semidefinite, and the smallest eigenvalue ofQis 0 if and only ifGis bipartite. We will study the separation of this eigenvalue from 0 in terms of the following measure of nonbipartiteness ofG.For anyS ⊆ V, we denote byemin(S) the minimum number of edges that need to be removed from the induced subgraph onSto make it bipartite. Also, we denote by cut(S) the set of edges with one end inSand the other inV−S. We define the parameter Ψ as.The parameter Ψ is a measure of the nonbipartiteness of the graphG. We will show that the smallest eigenvalue ofQis bounded above and below by functions of Ψ. Ford‐regular graphs, this characterizes the separation of the smallest eigenvalue of the adjacency matrix from −d. These results can be easily extended to

ISSN:0364-9024    

DOI:10.1002/jgt.3190180210

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

年代:1994

数据来源: WILEY

摘要:

AbstractA maximal independent set of a graphGis an independent set that is not contained properly in any other independent set ofG. Leti(G)denote the number of maximal independent sets ofG. Here, we prove two conjectures, suggested by P. Erdös, that the maximum number of maximal independent sets among all graphs of ordernin a family Φ iso(3n/3) if Φ is either a family of connected graphs such that the largest value of maximum degrees among all graphs of ordernin Φ iso(n)or a family of graphs such that the approaches infinity asn

ISSN:0364-9024    

DOI:10.1002/jgt.3190180211

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

年代:1994

数据来源: WILEY