Hypergraph families with bounded edge cover or transversal number

The transversal number, packing number, covering number and strong stability number of hypergraphs are denoted by τ, ν, ϱ and α, respectively. A hypergraph family t is called τ-bound (ϱ-bound) if there exists a “binding function”f(x) such that τ(H)≦f(v(H)) (ϱ(H)≦f(α(H))) for allH ∈ t. Methods are presented to show that various hypergraph families are τ-bound and/or ϱ-bound. The results can be applied to families of geometrical nature like subforests of trees, boxes, boxes of polyominoes or to families defined by hypergraph theoretic terms like the family where every subhypergraph has the Helly-property.     

Spanning trees with leaf distance at least four

For a graph G, we denote by i(G) the number of isolated vertices of G. We prove that for a connected graph G of order at least five, if i(G–S) < |S| for all ?? ≠ S ? V(G), then G has a spanning tree T such that the distance in T between any two leaves of T is at least four. This result was conjectured by Kaneko in “Spanning trees with constrains on the leaf degree”, Discrete Applied Math, 115 (2001), 73–76. Moreover, the condition in the result is sharp in a sense that the condition i(G–S) < |S| cannot be replaced by i(G–S) ≤ |S|. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 83–90, 2007     

The vertex (edge) independence number, vertex (edge) cover number and the least eigenvalue of a graph

In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all graphs of a fixed order and a given vertex (edge) independence number or vertex (edge) cover number, and get some bounds for the vertex (edge) independence number, vertex (edge) cover number of a graph in terms of the least eigenvalue of the graph.     

Reductions of 3-connected graphs with minimum degree at least four

We show that if G is a 3-connected graph of minimum degree at least 4 and with |V (G)| ≥ 7 then one of the following is true: (1) G has an edge e such that G/e is a 3-connected graph of minimum degree at least 4; (2) G has two edges uv and xy with ux, vy, vx ∈ E(G) such that the graph G/uv/xy obtained by contraction of edges uv and xy in G is a 3-connected graph of minimum degree at least 4; (3) G has a vertex x with N(x) = {x₁, x₂, x₃, x₄} and x₁x₂, x₃x₄ ∈ E(G) such that the graph (G ? x)/x₁x₂/x₃x₄ obtained by contraction of edges x₁x₂ and x₃x₄ in G – x is a 3-connected graph of minimum degree at least 4.

Each of the three reductions is necessary: there exists an infinite family of 3- connected graphs of minimum degree not less than 4 such that only one of the three reductions may be performed for the members of the family and not the two other reductions.     

Hypergraphs with cyclomatic number zero,triangulated graphs,and an inequality

A parameter μ for hypergraphs generalizing the cyclomatic number of graphs is defined. Theorem: a hypergraph has μ = 0 if and only if its edges maximal with respect to inclusion are the cliques of a triangulated graph. The equality μ = 0 immediately implies an inequality previously proved by L. Lovász and by P. Hansen and M. Las Vergnas for more restricted classes of hypergraphs.     

Graphs with least number of colorings

A λ-coloring of a graph G is an assignment of λ or fewer colors to the points of G so that no two adjacent points have the same color. Let Ω (n,e) be the collection of all connected n-point and e-edge graphs and let Ωp(n,e) be the planar graphs of Ω(n, e). This paper characterizes the graphs that minimize the number of λ-colorings in Ω(n, e) for all λ > 1 and Ωp(n,e) for all λ.4. © 1995 John Wiley & Sons, Inc.     

Free-convection layers at large prandtl number

Summary The behavior of laminar free-convection boundary layers at large Prandtl number is considered. Plane and axisymmetric flows are treated simultaneously in terms of a unified formulation. Flow and heat-transfer quantities are expressed in terms of expansions within an inner and an outer layer, both of which lie inside the Prandtl's viscous layer. The first two approximations are given in general and the first three approximation for self-similar flows. The inner solutions provide information on skin friction and heat transfer, whereas the outer solutions determine the mass flow rate induced by buoyancy. Numerical results are given for the selfsimilar flows.

---

Zusammenfassung Das Verhalten von laminaren Grenzschichten bei freier Konvektion wird für grosse Prandtl-Zahlen behandelt. Strömungs-und Wärmeübergangs-Grössen werden ausgedrückt mit Hilfe einer Entwicklung in einer inneren und äusseren Schicht, die beide innerhalb der Prandtlschen Reibungsschicht liegen. Die zwei ersten Näherungen des allgemeinen Falles werden angegeben, sowie die ersten drei Glieder für ähnliche Lösungen. Die innere Lösung ergibt die Reibung und den Wärmeübergang, während die äussere Lösung den durch Auftrieb induzierten Massenstrom liefert. Numerische Ergebnisse werden für Ähnlichkeits-Lösungen angegeben.

     

On 3-regular graphs having crossing number at least 2

We give a planar proof of the fact that if G is a 3-regular graph minimal with respect to having crossing number at least 2, then the crossing number of G is 2.     

超图的Alcuin数与其横贯数的关系

1000多年前, 英国著名学者Alcuin曾提出过一个古老的渡河问题, 即狼、羊和卷心菜的渡河问题. 最近, Prisner和Csorba等考虑了一般``冲突图"上的渡河问题. 将这一问题推广到超图$H=(V,\mathcal{E})$\,上, 考虑一类情况更一般的运输计划问题. 现在监管者 欲运输超图中的所有点\,(代表``items")\,渡河, 这里$V$的点子 形成超边 当且仅当这些点代表的``items"在无人监管的情况下不能留在一起. 超图$H$的Alcuin数是指超图$H$具有可行运输方案\,(即把$V$的点代表的``items" 全部运到河对岸)\,时船的最小容量. 给出了 $r$-一致完全二部超图和它的伴随超图, 以及$r$-一致超图的Alcuin数, 同时证明了判断$r$-一致超图是否为小船图是NP 困难的.     

Group divisible designs with large block sizes

For positive integers n, k with \(3\le k\le n\), let \(X=\mathbb {F}_{2^n}\setminus \{0,1\}\), \({\mathcal {G}}=\{\{x,x+1\}:x\in X\}\), and \({\mathcal {B}}_k=\left\{ \{x_1,x_2,\ldots ,x_k\}\!\subset \!X:\sum \limits _{i=1}^kx_i=1,\ \sum \limits _{i\in I}x_i\!\ne \!1\ \mathrm{for\ any}\ \emptyset \!\ne \!I\!\subsetneqq \!\{1,2,\ldots ,k\}\right\} \). Lee et al. used the inclusion–exclusion principle to show that the triple \((X,{\mathcal {G}},{\mathcal {B}}_k)\) is a \((k,\lambda _k)\)-GDD of type \(2^{2^{n-1}-1}\) for \(k\in \{3,4,5,6,7\}\) where \(\lambda _k=\frac{\prod _{i=3}^{k-1}(2^n-2^i)}{(k-2)!}\) (Lee et al. in Des Codes Cryptogr,  https://doi.org/10.1007/s10623-017-0395-8, 2017). They conjectured that \((X,{\mathcal {G}},{\mathcal {B}}_k)\) is also a \((k,\lambda _k)\)-GDD of type \(2^{2^{n-1}-1}\) for any integer \(k\ge 8\). In this paper, we use a similar construction and counting principles to show that there is a \((k,\lambda _k)\)-GDD of type \((q^2-q)^{(q^{n-1}-1)/(q-1)}\) for any prime power q and any integers k, n with \(3\le k\le n\) where \(\lambda _k=\frac{\prod _{i=3}^{k-1}(q^n-q^i)}{(k-2)!}\). Consequently, their conjecture holds. Such a method is also generalized to yield a \((k,\lambda _k)\)-GDD of type \((q^{\ell +1}-q^{\ell })^{(q^{n-\ell }-1)/(q-1)}\) where \(\lambda _k=\frac{\prod _{i=3}^{k-1}(q^n-q^{\ell +i-1})}{(k-2)!}\) and \(k+\ell \le n+1\).     

Wild algebras have one-point extensions of representation dimension at least four

We show that any wild algebra has a one-point extension of representation dimension at least four, and more generally that it has an n-point extension of representation dimension at least n+3. We give two explicit constructions, and obtain new examples of small algebras of representation dimension four.