摘要:

AbstractBounds are given on the number of colors required to color the edges of a graph (multigraph) such that each color appears at each vertexvat mostm(ν) times. The known results and proofs generalize in natural ways. Certain new edge‐coloring problems, which have no counterparts whenm(ν) = 1 for all ν ϵV, are st

ISSN:0364-9024    

DOI:10.1002/jgt.3190100202

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

年代:1986

数据来源: WILEY

摘要:

AbstractWe say that a digraph D has the odd cycle property if there exists an edge subset S such that every cycle of D has an odd number of edges from S. We give necessary and sufficient conditions for a digraph to have the odd cycle property. We also consider the analogous problem for graphs.

ISSN:0364-9024    

DOI:10.1002/jgt.3190100203

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

年代:1986

数据来源: WILEY

摘要:

AbstractWe examine the problem of finding a graphGwhosenth iterated clique graph has diameter equal to the diameter ofGplusn.

ISSN:0364-9024    

DOI:10.1002/jgt.3190100204

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

年代:1986

数据来源: WILEY

摘要:

AbstractIt is shown that for each rational numbert≥ 1 there exist infinitely many graphs with mean distance equal tot.For a graphG, define themean distanceμ(G) by\documentclass{article}\pagestyle{empty}\begin{document}$$ \mu \left(G \right) = \sum\limits_{\{x,y\} \subseteq V} {d\left({x,y} \right)} /\left({\frac{n}{2}} \right) $$\end{document}.In an earlier issue of this journal, J. Plesník [3, Theorem 9] showed that, given real numberst≥ 1 and ϵ>0, there exists a graphGwith |μ(G)−t|<ϵ. Furthermore, he asked [3, p. 19]: Given a rational numbert≥ 1, does there exist a graphGwith μ(G) =t? We answer this question in the affirmati

ISSN:0364-9024    

DOI:10.1002/jgt.3190100205

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

年代:1986

数据来源: WILEY

摘要:

AbstractA min‐max theorem for node coverings with odd chains in bipartite graphs is derived by simple network flow techniques. A characterization of minimum node covering in terms of a special kind of alternating chains is given, an extension of a result of Norman and Rabin on matchings and node coverings by edges is obtaine

ISSN:0364-9024    

DOI:10.1002/jgt.3190100206

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

年代:1986

数据来源: WILEY

摘要:

AbstractWe call a graph (m,k)‐colorable if its vertices can be colored withmcolors in such a way that each vertex is adjacent to at mostkvertices of the same color as itself. For the class of planar graphs, and the class of outerplanar graphs, we determine all pairs (m, k) such that every graph in the class is (m, k)‐colorable. We include an elementary proof (not assuming the truth of the four‐color theorem) that every planar graph is (4, 1)‐colorable. Finally, we prove that, for each compact surfaceS, there is an integerk=k(S)such that every graph inScan be (4,k)‐colored; we conjecture that 4 can be replaced by 3 in this

ISSN:0364-9024    

DOI:10.1002/jgt.3190100207

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

年代:1986

数据来源: WILEY

摘要:

AbstractGraham and Pollak [2] proved thatn– 1 is the minimum number of edge‐disjoint complete bipartite subgraphs into which the edges ofKndecompose. Tverberg [6], using a linear algebraic technique, was the first to give a simple proof of this result. We apply Tverberg's technique to obtain results for two related decomposition problems, in which we wish to partition the arcs/edges of complete digraphs/multigraphs into a minimum number of arc/edge‐disjoint complete bipartite subgraphs of appropriate natures. We obtain exact results for the digraph problem, which was posed by Lundgren and Maybee [4]. We also obtain exact results for the decomposition of complete multigraphs with exactly two edges connecting every pair of distinct ver

ISSN:0364-9024    

DOI:10.1002/jgt.3190100208

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

年代:1986

数据来源: WILEY

摘要:

AbstractLet F = {F1,…} be a given class of forbidden graphs. A graphGis called F‐saturated if noFi∈ F is a subgraph ofGbut the addition of an arbitrary new edge gives a forbidden subgraph. In this paper the minimal number of edges in F‐saturated graphs is examined. General estimations are given and the structure of minimal graphs is described for some special forbidden graphs (stars, paths,mpairwise disjoint

ISSN:0364-9024    

DOI:10.1002/jgt.3190100209

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

年代:1986

数据来源: WILEY

摘要:

AbstractWe prove that, with some exceptions, every digraph withn≥ 9 vertices and at least (n– 1) (n– 2) + 2 arcs contains all orientations of a Hamiltonian

ISSN:0364-9024    

DOI:10.1002/jgt.3190100210

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

年代:1986

数据来源: WILEY

摘要:

AbstractThis paper considers the (Δ,D) problem: to maximize the order of graphs with given maximum degree Δ and diameterD, of importance for its implications in the design of interconnection networks. Two cubic graphs of diameters 5 and 8 and orders 70 and 286, respectively, and a graph of degree 5, diameter 3 and order 66 are presented, which improve the previously known orders for these values of Δ andD. By its construction, these graphs have a large automorphism gro

ISSN:0364-9024    

DOI:10.1002/jgt.3190100211

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

年代:1986

数据来源: WILEY