摘要:

AbstractLetn≥ 1 be an integer and letGbe a graph. A setDof vertices inGis defined to be ann‐dominating set ofGif every vertex ofGis within distancenfrom some vertex ofD. The minimum cardinality among alln‐dominating sets of G is called the n‐domination numberofGand is denoted by γn(G). A set / of vertices inGisn‐irredundant if for every vertexx∈ / there exists a vertexythat is within distancenfromxbut at distance greater thannfrom every vertex of / ‐ {x}. The n‐irredundance number of G, denoted byirn(G), is the minimum cardinality taken over all maximaln‐irredundant sets of vertices ofG. We show that inf{irn(G)/γn(G) |Gis an arbitrary finite undirected graph with neither loops nor multiple edges} = 1/2 with the infimum not being attained. Subsequently, we show that 2/3 is a lower bound on all quotientsirn(T)/γn(T) in whichTis a tree. Furthermore, we show that, forn≥ 2, this bound is sharp. These results extend those of R. B. Allan and R.C. Laskar [“On Domination and Some Related Concepts in Graph Theory,”Utilitas Mathematica, Vol. 21 (1978), pp. 43–56], B. Bollobás and E. J. Cockayne [“Graph‐Theoretic Parameters Concerning Domination, Independence and Irredundance,”Journal of Graph Theory, Vol. 3 (1979), pp. 241–249], and P. Damaschke [Irredundance Number versus Domination Number,Discrete Math

ISSN:0364-9024    

DOI:10.1002/jgt.3190180102

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

年代:1994

数据来源: WILEY

摘要:

AbstractWe investigate the problem that at least how many edges must a maximal triangle‐free graph onnvertices have if the maximal valency is ≤D. Denote this minimum value byF(n, D). For large enoughn, we determine the exact value ofF(n, D) ifD≥ (n− 2)/2 and we prove that limF(n, cn)/n = K(c) exists for all 0

ISSN:0364-9024    

DOI:10.1002/jgt.3190180103

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

年代:1994

数据来源: WILEY

摘要:

AbstractA triangulation of a surface is locally cyclic if each cycle of length three in its 1‐skeleton bounds a face. It is shown that any locally cyclic triangulation of the projective plane can be obtained by repeatedly using the vertex splitting operation and starting with one of five minimal locally cyclic triangulation

ISSN:0364-9024    

DOI:10.1002/jgt.3190180104

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

年代:1994

数据来源: WILEY

摘要:

AbstractIt has previously been shown that ifMis a maximum matching in a 3‐connected graphG, other thanK4, thenMcontains at least one contractible edge ofG. In this paper, we give a constructive characterization of the 3‐connected graphsGhaving a maximum matching containing only one contractible edge

ISSN:0364-9024    

DOI:10.1002/jgt.3190180105

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

年代:1994

数据来源: WILEY

摘要:

AbstractLet G be an eulerian graph without odd block. It was proved by P. D. Seymour that ifGis planar, thenE(G) has a circuit decompositionFsuch that each circuit ofFis of even length. In this paper the theorem of Seymour is generalized: IfGcontains no subgraph contractible toK5, thenE(G) has an even circuit decomposition.

ISSN:0364-9024    

DOI:10.1002/jgt.3190180106

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

年代:1994

数据来源: WILEY

摘要:

AbstractA graphGof ordernsatisfies the neighborhood conditionNCk>sif any collection ofkindependent vertices is collectively adjacent to more than s vertices. Given a familyHof graphs, the decomposition class β(H) is the family of graphsBwith the property that for someH∈Hof chromatic numberd, HcontainsBas an induced subgraph and l̀V(H) −V(B)ǹ is (d− 2) colorable. LetHbe a family ofd‐chromatic graphs,Ban element of β(H) such thatBcontains ans‐matching as an induced subgraph. Thus the cardinality of one of the partite sets ofBis s +rfor some integerr≥ 0. We show that iftis a fixed positive integer,Gis a graph of sufficiently large ordernthat satisfies the neighborhood condition\documentclass{article}\pagestyle{empty}\begin{document}$$ NC_k > \frac{{\left({d - 2} \right)}}{{\left({d - 1} \right)}}n + cn^{1 -{1 \mathord{\left/{\vphantom{1 r}} \right. \kern-\nulldelimiterspace} r}}, $$\end{document}thenGcontainsB + K(d ‐2

ISSN:0364-9024    

DOI:10.1002/jgt.3190180107

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

年代:1994

数据来源: WILEY

摘要:

AbstractFor graphsGandFwe writeF→ (G)1rif everyr‐coloring of theverticesofFresults in a monochromatic copy ofG. The global densitym(F) ofFis the maximum ratio of the number of edges to the number of vertices taken over all subgraphs ofF. Let\documentclass{article}\pagestyle{empty}\begin{document}$$ m_{cr} \left({G,\,r} \right) = \inf \left\{{m\left(F \right):\,F \to \left(G \right)_r^1 } \right\}. $$\end{document}We show that\documentclass{article}\pagestyle{empty}\begin{document}$$ \frac{1}{2} \le \frac{{m_{cr} \left({G,\,r} \right)}}{{r\,\max _{H \subseteq G} \delta \left(H \right)}} r‐ ϵ for sufficiently largek, whereSkis the star withkarms. In particular, we prove that\documentclass{article}\pagestyle{empty}\begin{document}$$ \frac{4}{3} \le \,m_{cr} \left({S_2,\,2} \right) \le \,\frac{7}{5}. $$\end

ISSN:0364-9024    

DOI:10.1002/jgt.3190180108

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

年代:1994

数据来源: WILEY

摘要:

AbstractIn this paper all 2‐connectedk‐chromatic graphs of ordernwith the maximum sum of all distances between their vertices are characterized for everyk≥ 2, thus strengthening a result of J. Plesnik.Moreover, several auxiliary results are proved on chromatic critical graphs and 2‐connected

ISSN:0364-9024    

DOI:10.1002/jgt.3190180109

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

年代:1994

数据来源: WILEY

摘要:

AbstractThetoughness indexτ(G) of a graphGis defined to be the largest integertsuch that for anyS⊆V(G) with |S|>t,c(G ‐ S)<|S| ‐t, wherec(G‐S) denotes the number of components ofG‐S. In particular, 1‐tough graphs are exactly those graphs for which τ(G) ≥ 0. In this paper, it is shown that ifGis a planar graph, then τ(G) ≥ 2 if and only ifGis 4‐connected. This result suggests that there may be a polynomial‐time algorithm for determining whether a planar graph is 1‐tough, even though the problem for general graphs is NP‐hard. The result can be restated as follows: a planar graph is 4‐connected if and only if it remains 1‐tough whenever two vertices are removed. Hence it establishes a weakened version of a conjecture, due to M. D. Plummer, that removing 2 vertices from a 4‐connected planar

ISSN:0364-9024    

DOI:10.1002/jgt.3190180110

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

年代:1994

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190180101

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

年代:1994

数据来源: WILEY