摘要:

AbstractThe threshold weight of a graphGis introduced as a measure of the amount by whichGdiffers from being a threshold graph. The threshold graphs are precisely the graphs whose threshold weights are 0. At the opposite extreme is the class of graphs for which the threshold weight is the maximum possible. Such graphs are defined asheavy graphs.Among the results are as following: A theorem that specifies the threshold weight of any triangle‐free graph; necessary and sufficient conditions for a heavy graph in terms of the solvability of a system of linear inequalities; some sufficient conditions for a graph to be heavy and a necessary condition (conjectured to be sufficient, as well) for a heavy graph in terms of its clique

ISSN:0364-9024    

DOI:10.1002/jgt.3190150302

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

年代:1991

数据来源: WILEY

摘要:

AbstractWe extend Landau's concept of the score structure of a tournament to that of the score sequence of an oriented graph, and give a condition for an arbitrary integer sequence to be a score sequence. The proof is by construction of a specific oriented graph Δ(S) with given score sequenceS. It is shown that Δ(S) is transitive and has the minimum number of arcs among the oriented graphs with score sequence

ISSN:0364-9024    

DOI:10.1002/jgt.3190150303

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

年代:1991

数据来源: WILEY

摘要:

AbstractWe show that every connectedK1,3‐free graph with minimum degree at least2kcontains ak‐factor and construct connectedK1,3‐free graphs with minimum degreek+0(√k) that have nok

ISSN:0364-9024    

DOI:10.1002/jgt.3190150304

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

年代:1991

数据来源: WILEY

摘要:

AbstractWe show that between any two nodes of a cubic, planar, three‐connected graph there are three paths whose lengths are 0, 1, and 2 modulo 3, respectively. The proof is by a rather extensive case analysis. Counterexamples show that all three hypotheses (i.e., planarity, degree‐three, and three‐connectivity) are nece

ISSN:0364-9024    

DOI:10.1002/jgt.3190150305

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

年代:1991

数据来源: WILEY

摘要:

AbstractLetaandbbe integers withb⩾a⩾ 0. A graphGis called an [a,b]‐graph ifa⩽dG(v) ⩽bfor each vertexv∈V(G), and an [a,b]‐factor of a graphGis a spanning [a,b]‐subgraph ofG. A graph is [a,b]‐factorable if its edges can be decomposed into [a,b]‐factors. The purpose of this paper is to prove the following three theorems: (i) if 1 ⩽b⩽ 2a, every [(12a+ 2)m+ 2an,(12b+ 4)m+ 2bn]‐graph is [2a, 2b+ 1]‐factorable; (ii) ifb⩽ 2a−1, every [(12a−4)m+ 2an, (12b−2)m+ 2bn]‐graph is [2a−1,2b]‐factorable; and (iii) ifb⩽ 2a−1, every [(6a−2)m+ 2an, (6b+ 2)m+ 2bn]‐graph is [2a−1,2b+ 1]‐factorable, wheremandnare nonnegative integers. They generalize some [a,b]‐factorization

ISSN:0364-9024    

DOI:10.1002/jgt.3190150306

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

年代:1991

数据来源: WILEY

摘要:

AbstractLetU(n,M) be a graph chosen at random from the family of all unlabeled graphs withnvertices andMedges. In the paper we study the asymptotic behavior ofU(n,M) whenn→ ∞. In particular, we show how properties ofU(n,M) could be derived from analogous properties of a labeled random gr

ISSN:0364-9024    

DOI:10.1002/jgt.3190150307

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

年代:1991

数据来源: WILEY

摘要:

AbstractWe define two two‐variable polynomials for rooted trees and one two‐variable polynomial for unrooted trees, all of which are based on the coranknullity formulation of the Tutte polynomial of a graph or matroid. For the rooted polynomials, we show that the polynomial completely determines the rooted tree, i.e., rooted treesT1andT2are isomorphic if and only iff(T1) =f(T2). The corresponding question is open in the unrooted case, although we can reconstruct the degree sequence, number of subtrees of sizekfor allk, and the number of paths of lengthkfor allkfrom the (unrooted) polynomial. The key difference between these three polynomials and the standard Tutte polynomial is the rank function used; we use pruning and branching ranks to define the polynomials. We also give a subtree expansion of the polynomials and a deletion‐contraction recursion they sa

ISSN:0364-9024    

DOI:10.1002/jgt.3190150308

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

年代:1991

数据来源: WILEY

摘要:

AbstractFor a simple graph of maximum degree Δ, it is always possible to color the edges with Δ + 1 colors (Vizing); furthermore, if the set of vertices of maximum degree is independent, Δ colors suffice (Fournier). In this article, we give a short constructive proof of an extension of these results to multigraphs. Instead of considering several color interchanges along alternating chains (Vizing, Gupta), using counting arguments (Ehrenfeucht, Faber, Kierstead), or improving nonvalid colorings with Fournier's Lemma, the method of proof consists of using one single easy transformation, called “sequential recoloring”, to augment a partialk‐coloring of t

ISSN:0364-9024    

DOI:10.1002/jgt.3190150309

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

年代:1991

数据来源: WILEY

摘要:

AbstractA graph is said to beK1,n‐free, if it contains noK1,nas an induced subgraph. We prove that forn⩾ 3 andr⩾n−1, ifGis aK1,n‐free graph with minimum degree at least (n2/4(n−1))r+ (3n−6)/2 + (n−1)/4r, thenGhas anr‐factor (in the case whereris even, the conditionr⩾

ISSN:0364-9024    

DOI:10.1002/jgt.3190150310

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

年代:1991

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190150301

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

年代:1991

数据来源: WILEY