Pan-connectedness of graphs with large neighborhood unions

Let G be a simple graph with n vertices. For any v ? V(G){v \in V(G)} , let N(v)={u ? V(G): uv ? E(G)}{N(v)=\{u \in V(G): uv \in E(G)\}} , NC(G) = min{|N(u) èN(v)|: u, v ? V(G){NC(G)= \min \{|N(u) \cup N(v)|: u, v \in V(G)} and uv \not ? E(G)}{uv \not \in E(G)\}} , and NC₂(G) = min{|N(u) èN(v)|: u, v ? V(G){NC_2(G)= \min\{|N(u) \cup N(v)|: u, v \in V(G)} and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any u, v ? V(G){u, v \in V(G)} , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC ₂(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC ₂(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC ₂(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.     

THE TOTAL CHROMATIC NUMBER OF PSEUDO-OUTERPLANAR GRAPHS

A Planar graph g is called a ipseudo outerplanar graph if there is a subset v.∈V(G),[V.]=i,such that G-V. is an outerplanar graph in particular when G-V.is a forest ,g is called a i-pseudo-tree .in this paper.the following results are proved;(1)the conjecture on the total coloring is true for all 1-pseudo-outerplanar graphs;(2)X1(G) 1 fo any 1-pseudo outerplanar graph g with △(G)≥3,where x4(G)is the total chromatic number of a graph g.     

Large orbits of elements centralized by a Sylow subgroup

If G has a nilpotent normal p-complement and V is a finite, faithful and completely reducible G-module of characteristic p, we prove that there exist ${v_1, v_2 \in V}If G has a nilpotent normal p-complement and V is a finite, faithful and completely reducible G-module of characteristic p, we prove that there exist v₁, v₂ ? V{v_1, v_2 \in V} such that C_G(v₁)?C_G(v₂) = P{{\bf C}_{G}{(v_1)}\cap {\bf C}_{G}{(v_2)} = P} , where P ? Syl_p(G){P \in {\rm Syl}_p(G)} . We hence deduce that, if the normal p-complement K is nontrivial, there exists v ? C_V(P){v \in {\bf C}_{V}(P)} such that |K : C _K (v)|² > |K|.     

Roman domination subdivision number of graphs

A Roman dominating function on a graph G = (V, E) is a function f : V ? {0, 1, 2}f : V \rightarrow \{0, 1, 2\} satisfying the condition that every vertex v for which f(v) = 0 is adjacent to at least one vertex u for which f(u) = 2. The weight of a Roman dominating function is the value w(f) = ?_{v ? V} f(v)w(f) = \sum_{v\in V} f(v). The Roman domination number of a graph G, denoted by _gR(G)_{\gamma R}(G), equals the minimum weight of a Roman dominating function on G. The Roman domination subdivision number sd_gR(G)sd_{\gamma R}(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the Roman domination number. In this paper, first we establish upper bounds on the Roman domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on G which are sufficient to imply that $1 \leq sd_{\gamma R}(G) \leq 3$1 \leq sd_{\gamma R}(G) \leq 3. Finally, we show that the Roman domination subdivision number of a graph can be arbitrarily large.     

Eigenvalues and homology of flag complexes and vector representations of graphs

The flag complex of a graph G = (V, E) is the simplicial complex X(G) on the vertex set V whose simplices are subsets of V which span complete subgraphs of G. We study relations between the first eigenvalues of successive higher Laplacians of X(G). One consequence is the following:Theorem: Let λ₂(G) denote the second smallest eigenvalue of the Laplacian of G. If \,\frac{k}{k+1}|V|$$" align="middle" border="0"> then Applications include a lower bound on the homological connectivity of the independent sets complex I(G), in terms of a new graph domination parameter Γ(G) defined via certain vector representations of G. This in turns implies Hall type theorems for systems of disjoint representatives in hypergraphs.Received: January 2004 Revised: August 2004 Accepted: August 2004     

Total Domination in Partitioned Graphs

We present results on total domination in a partitioned graph G = (V, E). Let γ _t (G) denote the total dominating number of G. For a partition , k ≥ 2, of V, let γ _t (G; V _i ) be the cardinality of a smallest subset of V such that every vertex of V _i has a neighbour in it and define the following

On the Roman Bondage Number of Planar Graphs

A Roman dominating function on a graph G is a function f : V(G) → {0, 1, 2} satisfying the condition that every vertex u for which f (u) = 0 is adjacent to at least one vertex v for which f (v) = 2. The weight of a Roman dominating function is the value f (V(G)) = ?_{u ? V(G)} f (u){f (V(G)) = \sum_{u\in V(G)} f (u)}. The Roman domination number, γ _R (G), of G is the minimum weight of a Roman dominating function on G. The Roman bondage number b _R (G) of a graph G with maximum degree at least two is the minimum cardinality of all sets E^￠ í E(G){E^{\prime} \subseteq E(G)} for which γ _R (G − E′) > γ _R (G). In this paper we present different bounds on the Roman bondage number of planar graphs.     

An Introduction to Closed/Open Neighborhood Sums: Minimax, Maximin, and Spread

For a graph G of order |V(G)| = n and a real-valued mapping f:V(G)?\mathbbR{f:V(G)\rightarrow\mathbb{R}}, if S ì V(G){S\subset V(G)} then f(S)=?_{w ? S} f(w){f(S)=\sum_{w\in S} f(w)} is called the weight of S under f. The closed (respectively, open) neighborhood sum of f is the maximum weight of a closed (respectively, open) neighborhood under f, that is, NS[f]=max{f(N[v])|v ? V(G)}{NS[f]={\rm max}\{f(N[v])|v \in V(G)\}} and NS(f)=max{f(N(v))|v ? V(G)}{NS(f)={\rm max}\{f(N(v))|v \in V(G)\}}. The closed (respectively, open) lower neighborhood sum of f is the minimum weight of a closed (respectively, open) neighborhood under f, that is, NS^-[f]=min{f(N[v])|v ? V(G)}{NS^{-}[f]={\rm min}\{f(N[v])|v\in V(G)\}} and NS^-(f)=min{f(N(v))|v ? V(G)}{NS^{-}(f)={\rm min}\{f(N(v))|v\in V(G)\}}. For W ì \mathbbR{W\subset \mathbb{R}}, the closed and open neighborhood sum parameters are NS_W[G]=min{NS[f]|f:V(G)? W{NS_W[G]={\rm min}\{NS[f]|f:V(G)\rightarrow W} is a bijection} and NS_W(G)=min{NS(f)|f:V(G)? W{NS_W(G)={\rm min}\{NS(f)|f:V(G)\rightarrow W} is a bijection}. The lower neighbor sum parameters are NS^-_W[G]=maxNS^-[f]|f:V(G)? W{NS^{-}_W[G]={\rm max}NS^{-}[f]|f:V(G)\rightarrow W} is a bijection} and NS^-_W(G)=maxNS^-(f)|f:V(G)? W{NS^{-}_W(G)={\rm max}NS^{-}(f)|f:V(G)\rightarrow W} is a bijection}. For bijections f:V(G)? {1,2,?,n}{f:V(G)\rightarrow \{1,2,\ldots,n\}} we consider the parameters NS[G], NS(G), NS ⁻[G] and NS ⁻(G), as well as two parameters minimizing the maximum difference in neighborhood sums.     

A bound on the <Emphasis Type="Italic">k</Emphasis>-domination number of a graph

Let G be a graph with vertex set V(G), and let k ⩾ 1 be an integer. A subset D ⊆ V(G) is called a k-dominating set if every vertex υ ∈ V(G)-D has at least k neighbors in D. The k-domination number γ _k (G) of G is the minimum cardinality of a k-dominating set in G. If G is a graph with minimum degree δ(G) ⩾ k + 1, then we prove that

Recurrent approach to Blaschke’s problem

We have obtained a recurrence formula $I_{n+3} = \frac{4(n+3)}{\pi(n+4)}VI_{n+1}We have obtained a recurrence formula I_n+3 = \frac4(n+3)p(n+4)VI_n+1I_{n+3} = \frac{4(n+3)}{\pi(n+4)}VI_{n+1} for integro-geometric moments in the case of a circle with the area V, where I_n = ò\nolimits_{K ?G}sⁿd GI_n = \int \nolimits_{K \cap G}\sigma^{n}{\rm d} G, while in the case of a convex domain K with the perimeter S and area V the recurrence formula

In+3 = \frac8(n+3)V2(n+1)(n+4)p[\fracd In+1d V - \fracIn+1S \fracd Sd V ] I_{n+3} = \frac{8(n+3)V^2}{(n+1)(n+4)\pi}\Big[\frac{{\rm d} I_{n+1}}{{\rm d} V} - \frac{I_{n+1}}{S} \frac{{\rm d} S}{{\rm d} V} \Big]      11. Straightening and bounded cohomology of hyperbolic groups   总被引：2，自引：0，他引：2   I. Mineyev 《Geometric And Functional Analysis》2001,11(4):807-839 It was stated by M. Gromov [Gr2] that, for any hyperbolic group G, the map from bounded cohomology Hnb(G,\Bbb R) H^n_b(G,{\Bbb R}) to Hn(G,\Bbb R) H^n(G,{\Bbb R}) induced by inclusion is surjective for n 3 2 n \ge 2 . We introduce a homological analogue of straightening simplices, which works for any hyperbolic group. This implies that the map Hnb(G,V) ? Hn(G,V) H^n_b(G,V) \to H^n(G,V) is surjective for n 3 2 n \ge 2 when V is any bounded \Bbb QG {\Bbb Q}G -module and when V is any finitely generated abelian group.      12. Rooted induced trees in triangle‐free graphs      Florian Pfender 《Journal of Graph Theory》2010,64(3):206-209 For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t3(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceilFor a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t3(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceil$, improving a recent result by Fox, Loh and Sudakov. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 206–209, 2010      13. Analysis of the impact of the number of edges in connected graphs on the computational complexity of the independent set problem      D. S. Malyshev 《Journal of Applied and Industrial Mathematics》2012,6(1):97-99 Under study is the complexity status of the independent set problem in a class of connected graphs that are defined by functional constraints on the number of edges depending on the number of vertices. For every natural number C, this problem is shown to be polynomially solvable in the class of graphs èn = 1￥ { G:|V(G)| = n,|E(G)| \leqslant n + C[log2 (n)]} . \bigcup\limits_{n = 1}^\infty {\{ G:|V(G)| = n,|E(G)| \leqslant n + C[\log _2 (n)]\} .}      14. Central Extensions of Steinberg Lie Superalgebras of Small Rank      Shikui Shang  Hongjia Chen 《代数通讯》2013,41(12):4225-4244 It was shown by Mikhalev and Pinchuk (2000 Mikhalev , A. V. , Pinchuk , I. A. ( 2000 ). Universal central extensions of the matrix Lie superalgebras sl(m,n,A) . Int. Conf. in H.K.U., AMS , 111 – 125 . [Google Scholar]) that the second homology group H 2(𝔰𝔱(m,n,R)) of the Steinberg Lie superalgebra 𝔰𝔱(m,n,R) is trivial for m + n ≥ 5. In this article, we will work out H 2(𝔰𝔱(m,n,R)) explicitly for m + n = 3, 4.      15. An Upper Bound for the Total Domination Subdivision Number of a Graph      H. Karami  R. Khoeilar  S. M. Sheikholeslami  A. Khodkar 《Graphs and Combinatorics》2009,25(5):727-733 A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdgt(G){{\rm sd}_{\gamma_t}(G)} is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper, we prove that sdgt(G) ￡ 2gt(G)-1{{\rm sd}_{\gamma_t}(G)\leq 2\gamma_t(G)-1} for every simple connected graph G of order n ≥ 3.      16. Ordering the non-starlike trees with large reverse wiener indices      Shuxian Li  Bo Zhou 《Czechoslovak Mathematical Journal》2012,62(1):215-233 The reverse Wiener index of a connected graph G is defined as { L (G) = 1/2n(n - 1)d - W(G)\Lambda (G) = {1 \over 2}n(n - 1)d - W(G)      17. Balanced judicious bipartitions of graphs      Baogang Xu  Juan Yan  Xingxing Yu 《Journal of Graph Theory》2010,63(3):210-225 A bipartition of the vertex set of a graph is called balanced if the sizes of the sets in the bipartition differ by at most one. B. Bollobás and A. D. Scott, Random Struct Alg 21 (2002), 414–430 conjectured that if G is a graph with minimum degree of at least 2 then V(G) admits a balanced bipartition V1, V2 such that for each i, G has at most |E(G)|/3 edges with both ends in Vi. The minimum degree condition is necessary, and a result of B. Bollobás and A. D. Scott, J. Graph Theory 46 (2004), 131–143 shows that this conjecture holds for regular graphs G(i.e., when Δ(G)=δ(G)). We prove this conjecture for graphs G with \begin{eqnarray*}\Delta(G)\le\frac{7}{5}\delta(G)\end{eqnarray*}; hence, it holds for graphs ]ensuremathG with \begin{eqnarray*}\delta(G)\ge\frac{5}{7}|V(G)|\end{eqnarray*}. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 210–225, 2010      18. Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree      Nathann Cohen  Fr��d��ric Havet 《Graphs and Combinatorics》2011,27(6):831-849 A proper vertex colouring of a graph G is 2-frugal (resp. linear) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph G is 2-frugally (resp. linearly) L-colourable if for a given list assignment L:V(G)? 2\mathbb N{L:V(G)\mapsto 2^{\mathbb N}} , there exists a 2-frugal (resp. linear) colouring c of G such that c(v) ? L(v){c(v) \in L(v)} for all v ? V(G){v\in V(G)} . If G is 2-frugally (resp. linearly) L-list colourable for any list assignment such that |L(v)| ≥ k for all v ? V(G){v\in V(G)}, then G is 2-frugally (resp. linearly) k-choosable. In this paper, we improve some bounds on the 2-frugal choosability and linear choosability of graphs with small maximum average degree.      19. Reconstructing graphs as subsumed graphs of hypergraphs,and some self-complementary triple systems      William Kocay 《Graphs and Combinatorics》1992,8(3):259-276 LetV be a set ofn elements. The set of allk-subsets ofV is denoted . Ak-hypergraph G consists of avertex-set V(G) and anedgeset , wherek≥2. IfG is a 3-hypergraph, then the set of edges containing a given vertexvεV(G) define a graphG v . The graphs {G v νvεV(G)} aresubsumed byG. Each subsumed graphG v is a graph with vertex-setV(G) − v. They can form the set of vertex-deleted subgraphs of a graphH, that is, eachG v ≽H −v, whereV(H)=V(G). In this case,G is a hypergraphic reconstruction ofH. We show that certain families of self-complementary graphsH can be reconstructed in this way by a hypergraphG, and thatG can be extended to a hypergraphG *, all of whose subsumed graphs are isomorphic toH, whereG andG * are self-complementary hypergraphs. In particular, the Paley graphs can be reconstructed in this way. This work was supported by an operating grant from the Natural Sciences and Engineering Research Council of Canada.      20. The k-Restricted Edge Connectivity of Balanced Bipartite Graphs      Jun Yuan  Aixia Liu 《Graphs and Combinatorics》2011,27(2):289-303 For a connected graph G = (V, E), an edge set S ì E{S\subset E} is called a k-restricted edge cut if G − S is disconnected and every component of G − S contains at least k vertices. The k-restricted edge connectivity of G, denoted by λ k (G), is defined as the cardinality of a minimum k-restricted edge cut. For two disjoint vertex sets U1,U2 ì V(G){U_1,U_2\subset V(G)}, denote the set of edges of G with one end in U 1 and the other in U 2 by [U 1, U 2]. Define xk(G)=min{|[U,V(G)\ U]|: U{\xi_k(G)=\min\{|[U,V(G){\setminus} U]|: U} is a vertex subset of order k of G and the subgraph induced by U is connected}. A graph G is said to be λ k -optimal if λ k (G) = ξ k (G). A graph is said to be super-λ k if every minimum k-restricted edge cut is a set of edges incident to a certain connected subgraph of order k. In this paper, we present some degree-sum conditions for balanced bipartite graphs to be λ k -optimal or super-λ k . Moreover, we demonstrate that our results are best possible.      设为首页 | 免责声明 | 关于勤云 | 加入收藏 Copyright©北京勤云科技发展有限公司  京ICP备09084417号

Straightening and bounded cohomology of hyperbolic groups

It was stated by M. Gromov [Gr2] that, for any hyperbolic group G, the map from bounded cohomology Hⁿ_b(G,\Bbb R) H^n_b(G,{\Bbb R}) to Hⁿ(G,\Bbb R) H^n(G,{\Bbb R}) induced by inclusion is surjective for n 3 2 n \ge 2 . We introduce a homological analogue of straightening simplices, which works for any hyperbolic group. This implies that the map Hⁿ_b(G,V) ? Hⁿ(G,V) H^n_b(G,V) \to H^n(G,V) is surjective for n 3 2 n \ge 2 when V is any bounded \Bbb QG {\Bbb Q}G -module and when V is any finitely generated abelian group.     

Rooted induced trees in triangle‐free graphs

For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t₃(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceilFor a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t₃(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceil$, improving a recent result by Fox, Loh and Sudakov. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 206–209, 2010     

Analysis of the impact of the number of edges in connected graphs on the computational complexity of the independent set problem

Under study is the complexity status of the independent set problem in a class of connected graphs that are defined by functional constraints on the number of edges depending on the number of vertices. For every natural number C, this problem is shown to be polynomially solvable in the class of graphs

Central Extensions of Steinberg Lie Superalgebras of Small Rank

It was shown by Mikhalev and Pinchuk (2000 Mikhalev , A. V. , Pinchuk , I. A. ( 2000 ). Universal central extensions of the matrix Lie superalgebras sl(m,n,A) . Int. Conf. in H.K.U., AMS , 111 – 125 . [Google Scholar]) that the second homology group H ₂(𝔰𝔱(m,n,R)) of the Steinberg Lie superalgebra 𝔰𝔱(m,n,R) is trivial for m + n ≥ 5. In this article, we will work out H ₂(𝔰𝔱(m,n,R)) explicitly for m + n = 3, 4.     

An Upper Bound for the Total Domination Subdivision Number of a Graph

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_gt(G){{\rm sd}_{\gamma_t}(G)} is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper, we prove that sd_gt(G) ￡ 2g_t(G)-1{{\rm sd}_{\gamma_t}(G)\leq 2\gamma_t(G)-1} for every simple connected graph G of order n ≥ 3.     

Ordering the non-starlike trees with large reverse wiener indices

The reverse Wiener index of a connected graph G is defined as {

Balanced judicious bipartitions of graphs

A bipartition of the vertex set of a graph is called balanced if the sizes of the sets in the bipartition differ by at most one. B. Bollobás and A. D. Scott, Random Struct Alg 21 (2002), 414–430 conjectured that if G is a graph with minimum degree of at least 2 then V(G) admits a balanced bipartition V₁, V₂ such that for each i, G has at most |E(G)|/3 edges with both ends in V_i. The minimum degree condition is necessary, and a result of B. Bollobás and A. D. Scott, J. Graph Theory 46 (2004), 131–143 shows that this conjecture holds for regular graphs G(i.e., when Δ(G)=δ(G)). We prove this conjecture for graphs G with \begin{eqnarray*}\Delta(G)\le\frac{7}{5}\delta(G)\end{eqnarray*}; hence, it holds for graphs ]ensuremathG with \begin{eqnarray*}\delta(G)\ge\frac{5}{7}|V(G)|\end{eqnarray*}. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 210–225, 2010     

Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree

A proper vertex colouring of a graph G is 2-frugal (resp. linear) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph G is 2-frugally (resp. linearly) L-colourable if for a given list assignment L:V(G)? 2^{\mathbb N}{L:V(G)\mapsto 2^{\mathbb N}} , there exists a 2-frugal (resp. linear) colouring c of G such that c(v) ? L(v){c(v) \in L(v)} for all v ? V(G){v\in V(G)} . If G is 2-frugally (resp. linearly) L-list colourable for any list assignment such that |L(v)| ≥ k for all v ? V(G){v\in V(G)}, then G is 2-frugally (resp. linearly) k-choosable. In this paper, we improve some bounds on the 2-frugal choosability and linear choosability of graphs with small maximum average degree.     

Reconstructing graphs as subsumed graphs of hypergraphs,and some self-complementary triple systems

LetV be a set ofn elements. The set of allk-subsets ofV is denoted . Ak-hypergraph G consists of avertex-set V(G) and anedgeset , wherek≥2. IfG is a 3-hypergraph, then the set of edges containing a given vertexvεV(G) define a graphG _v . The graphs {G _v νvεV(G)} aresubsumed byG. Each subsumed graphG _v is a graph with vertex-setV(G) − v. They can form the set of vertex-deleted subgraphs of a graphH, that is, eachG _v ≽H −v, whereV(H)=V(G). In this case,G is a hypergraphic reconstruction ofH. We show that certain families of self-complementary graphsH can be reconstructed in this way by a hypergraphG, and thatG can be extended to a hypergraphG ^*, all of whose subsumed graphs are isomorphic toH, whereG andG ^* are self-complementary hypergraphs. In particular, the Paley graphs can be reconstructed in this way. This work was supported by an operating grant from the Natural Sciences and Engineering Research Council of Canada.     

The k-Restricted Edge Connectivity of Balanced Bipartite Graphs

For a connected graph G = (V, E), an edge set S ì E{S\subset E} is called a k-restricted edge cut if G − S is disconnected and every component of G − S contains at least k vertices. The k-restricted edge connectivity of G, denoted by λ _k (G), is defined as the cardinality of a minimum k-restricted edge cut. For two disjoint vertex sets U₁,U₂ ì V(G){U_1,U_2\subset V(G)}, denote the set of edges of G with one end in U ₁ and the other in U ₂ by [U ₁, U ₂]. Define x_k(G)=min{|[U,V(G)\ U]|: U{\xi_k(G)=\min\{|[U,V(G){\setminus} U]|: U} is a vertex subset of order k of G and the subgraph induced by U is connected}. A graph G is said to be λ _k -optimal if λ _k (G) = ξ _k (G). A graph is said to be super-λ _k if every minimum k-restricted edge cut is a set of edges incident to a certain connected subgraph of order k. In this paper, we present some degree-sum conditions for balanced bipartite graphs to be λ _k -optimal or super-λ _k . Moreover, we demonstrate that our results are best possible.