摘要:

AbstractA vertexvof a graphGis calledgroupieif the average degreetvof all neighbors ofvinGis not smaller than the average degreetGofG.Every graph contains a groupie vertex; the problem of whether or not every simple graph on ≧2 vertices has at least two groupie vertices turned out to be surprisingly difficult. We present various sufficient conditions for a simple graph to contain at least two groupie vertices. Further, we investigate the functionf(n) = max minv(tv/tG), where the maximum ranges over all simple graphs onnvertices, and prove thatf(n) = 1/42n+o(1). The corresponding result for multigraphs is in sharp contrast with the above. We also characterize trees in which the local average degreetvis constan

ISSN:0364-9024    

DOI:10.1002/jgt.3190180702

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

年代:1994

数据来源: WILEY

摘要:

AbstractFor several years, the study of neighborhood unions of graphs has given rise to important structural consequences of graphs. In particular, neighborhood conditions that give rise to hamiltonian cycles have been considered in depth. In this paper we generalize these approaches to give a bound on the smallest number of cycles inGcontaining all the vertices ofG.We show that if for allx,y≅V(G), |N(x) ∩N(y)| ≧ 2n/5 + 1, thenV(G) is coverable by at most two cycles. Several related results and extensions totcycles are also

ISSN:0364-9024    

DOI:10.1002/jgt.3190180703

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

年代:1994

数据来源: WILEY

摘要:

AbstractSupposeG = (V, E)is a graph in which every vertexxhas a non‐negative real numberw(x)as its weight. Thew‐distance sum of a vertexyisDG, w(y)= σx≅vd(y, x)w(x).Thew‐median ofGis the set of all verticesywith minimumw‐distance sumDG,w(y).This paper shows that thew‐median of a connected strongly chordal graphGis a clique whenw(x)is positive for all

ISSN:0364-9024    

DOI:10.1002/jgt.3190180704

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

年代:1994

数据来源: WILEY

摘要:

AbstractScattered through the literature various structures occur that generalize median graphs and median algebras: quasi‐median graphs, retracts of Hamming graphs, graphs of finite windex, isotropic media, subdirect products of simplex algebras, certain ternary algebras, and so on. We connect them all up, provide some new generalizations of quasi‐median graphs, some new sets of axioms for quasi‐median algebras, and some shorter proofs as

ISSN:0364-9024    

DOI:10.1002/jgt.3190180705

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

年代:1994

数据来源: WILEY

摘要:

AbstractA kernel of a directed graph is a set of verticesKthat is both absorbant and independent (i.e., every vertex not inKis the origin of an arc whose extremity is inK, and no arc of the graph has both endpoints inK). In 1983, Meyniel conjectured that any perfect graph, directed in such a way that every circuit of length three uses two reversible arcs, must have a kernel. This conjecture was proved for parity graphs. In this paper, we extend that result and prove that Meyniel's conjecture holds for all graphs in which every odd cycle has two chords.

ISSN:0364-9024    

DOI:10.1002/jgt.3190180706

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

年代:1994

数据来源: WILEY

摘要:

AbstractA graph is well covered if every maximal independent set has the same cardinality. A vertexx, in a well‐covered graphG, is called extendable ifG – {x}is well covered and β(G) = β(G – {x}). IfGis a connected, well‐covered graph containing no 4‐ nor 5‐cycles as subgraphs andGcontains an extendable vertex, thenGis the disjoint union of edges and triangles together with a restricted set of edges joining extendable vertices. There are only 3 other connected, well‐covered graphs of this type that do not contain an extendable vertex. Moreover, all these graphs can be recognized in

ISSN:0364-9024    

DOI:10.1002/jgt.3190180707

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

年代:1994

数据来源: WILEY

摘要:

AbstractA graph isk‐domination‐critical if γ(G) = k, and for any edgeenot inG, γ(G + e) = k− 1. In this paper we show that the diameter of a dominationk‐critical graph withk≧ 2 is at most 2k− 2. We also show that for everyk≧ 2, there is ak‐domination‐critical graph having diameter [(3/2)k− 1]. We also show that the diameter of a 4‐domination‐cr

ISSN:0364-9024    

DOI:10.1002/jgt.3190180708

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

年代:1994

数据来源: WILEY

摘要:

AbstractIn this paper we examine self‐dual embeddings of complete multipartite graphs, focusing primarily onKm(n)havingmparts each of sizen.Ifm= 2, thennmust be even. If the embedding is on an orientable surface, then an Euler characteristic argument shows that no such embedding exists whennis odd andm 2, 3 (mod 4); there is no such restriction for embeddings on nonorientable surfaces. We show that these embeddings exist with a few small exceptions. As a corollary, every group has a Cayley graph with a self‐dual embedding. Our main technique is an addition construction that combines self‐dual embeddings of two subgraphs into a self‐dual embedding of their union. We also apply this technique to nonregular multipartite graphs and

ISSN:0364-9024    

DOI:10.1002/jgt.3190180709

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

年代:1994

数据来源: WILEY

摘要:

AbstractIn this article, we develop a theory of walks traversing every edge exactly twice. Rosenstiehl and Read proved that ifGis a graph with no set of edges that is simultaneously a cycle and a cocycle, thenGis planar if and only if there is a closed walkWinGtraversing every edge exactly twice such that certain sets of edges derived fromWare all cocycles. One consequence of the current work is a simple proof of the Rosenstiehl‐Read theorem. Another is an unusual method for determining the rank (over the integers modulo 2) of a symmetric matrix obtained from a circle grap

ISSN:0364-9024    

DOI:10.1002/jgt.3190180710

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

年代:1994

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190180701

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

年代:1994

数据来源: WILEY