ISSN:0364-9024    

DOI:10.1002/jgt.3190140502

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

年代:1990

数据来源: WILEY

摘要:

AbstractLetCbe the class of triangle‐free graphs with maximum degree at most three. A lower bound for the number of edges in a graph ofCis derived in terms of the number of vertices and the independence. Several classes of graphs for which this bound is attained are given. As corollaries, we obtain the best possible lower bound for the independence ratio of a graph inCand evaluate some Ramsey‐type numb

ISSN:0364-9024    

DOI:10.1002/jgt.3190140503

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

年代:1990

数据来源: WILEY

摘要:

AbstractIt was conjectured by Fan that if a graphG= (V,E) has a nowhere‐zero 3‐flow, thenGcan be covered by two even subgraphs of total size at most |V| + |E| ‐ 3. This conjecture is proved in this paper. It is also proved in this paper that the optimum solution of the Chinese postman problem and the solution of minimum cycle covering problem are equivalent for any graph admitting a nowhere‐zero

ISSN:0364-9024    

DOI:10.1002/jgt.3190140504

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

年代:1990

数据来源: WILEY

摘要:

AbstractLetCν(T) denote the “cover time” of the treeTfrom the vertexv, that is, the expected number of steps before a random walk starting atvhits every vertex ofT.Asymptotic lower bounds forCν(T) (forTa tree onnvertices) have been obtained recently by Kahn, Linial, Nisan and Saks, and by Devroye and Sbihi; here, we obtain the exact lower bound (approximately 2nInn) by showing thatCν(T) is minimized whenTis a star andvis one of its leaves.In addition, we show that the time to cover all vertices and then return to the starting point is minimized by a star (beginning at the center) and maximized by a path (beginning at one of the

ISSN:0364-9024    

DOI:10.1002/jgt.3190140505

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe characterize (by forbidden induced subgraphs) those line‐graphs that are perfectly orderable. Implicit in our presentation is a polynomial, time algorithm for recognizing these graph

ISSN:0364-9024    

DOI:10.1002/jgt.3190140506

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe describe an algorithm for cataloging graphs by generating them uniformly at random. The method used is based on a recent algorithm by Dixon and Wilf that generates orbit representatives uniformly at random. The approach is refined to graphs with prescribed numbers of edges and vertices, and then applied to obtain the complete list of graphs on 10 vertices.

ISSN:0364-9024    

DOI:10.1002/jgt.3190140507

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

年代:1990

数据来源: WILEY

摘要:

AbstractWhen can ak‐edge‐coloring of a subgraphKof a graphGbe extended to ak‐edge‐coloring ofG? One necessary condition is that\documentclass{article}\pagestyle{empty}\begin{document}$$ |{\rm X}|\, \le \,\sum\limits_{1 \le {\rm i} \le {\rm k}} {\mu _i ({\rm X})} $$\end{document}for allX ⊆ E(G) ‐E(K), where μi(X) is the maximum cardinality of a subset ofXwhose union with the set of edges ofKcolorediis a matching. This condition is not sufficient in general, but is sufficient for graphs of very simple structure. We try to locate the border where suff

ISSN:0364-9024    

DOI:10.1002/jgt.3190140508

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

年代:1990

数据来源: WILEY

摘要:

AbstractIn the graphKm×Kma 4‐cycle is called square if its vertices do not all lie in the same copy ofKm. Ac‐coloring of the edges ofKm×Kmis good if in any square 4‐cycle the two edges of at least one nonadjacent pair receive different colors. Letf(2,c) denote the smallest integermso that noc‐coloring ofKm×Kmis good. We show that there exists a constantkso thatf(2,c)>kc3. (This function was introduced by Shelah in his proof of van der Waerden'

ISSN:0364-9024    

DOI:10.1002/jgt.3190140509

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

年代:1990

数据来源: WILEY

摘要:

AbstractThe Steiner distance of a setSof vertices in a connected graphGis the minimum size among all connected subgraphs ofGcontainingS.Forn≥ 2, then‐eccentricityen(ν) of a vertex ν of a graphGis the maximum Steiner distance among all setsSofnvertices ofGthat contains ν. Then‐diameter ofGis the maximumn‐eccentricity among the vertices ofGwhile then‐radius ofGis the minimumn‐eccentricity. Then‐center ofGis the subgraph induced by those vertices ofGhaving minimumn‐eccentricity. It is shown that every graph is then‐center of some graph. Several results on then‐center of a tree are established. In particular, it is shown that then‐center of a tree is a tree and those trees that aren‐centers

ISSN:0364-9024    

DOI:10.1002/jgt.3190140510

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe shall prove that ifLis a 3‐chromatic (so called “forbidden”) graph, and —Rnis a random graph onnvertices, whose edges are chosen independently, with probabilityp, and —Bnis a bipartite subgraph ofRnof maximum size, —Fnis anL‐free subgraph ofRnof maximum size, then (in some sense)FnandBnare very near to each other: almost surely they have almost the same number of edges, and one can deleteOp(1) edges fromFnto obtain a bipartite graph. Moreover, withp= 1/2 andLany odd cycle,Fnis almost sur

ISSN:0364-9024    

DOI:10.1002/jgt.3190140511

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

年代:1990

数据来源: WILEY