Sufficient Conditions for a Digraph to be Supereulerian

A (di)graph is supereulerian if it contains a spanning eulerian sub(di)graph. This property is a relaxation of hamiltonicity. Inspired by this analogy with hamiltonian cycles and by similar results in supereulerian graph theory, we analyze a number of sufficient Ore type conditions for a digraph to be supereulerian. Furthermore, we study the following conjecture due to Thomassé and the first author: if the arc‐connectivity of a digraph is not smaller than its independence number, then the digraph is supereulerian. As a support for this conjecture we prove it for digraphs that are semicomplete multipartite or quasitransitive and verify the analogous statement for undirected graphs.     

Mesoporous Silica Nanoparticles Decorated with Carbosilane Dendrons as New Non‐viral Oligonucleotide Delivery Carriers

A novel nanosystem based on mesoporous silica nanoparticles covered with carbosilane dendrons grafted on the external surface of the nanoparticles is reported. This system is able to transport single‐stranded oligonucleotide into cells, avoiding an electrostatic repulsion between the cell membrane and the negatively charged nucleic acids thanks to the cationic charge provided by the dendron coating under physiological conditions. Moreover, the presence of the highly ordered pore network inside the silica matrix would make possible to allocate other therapeutic agents within the mesopores with the aim of achieving a double delivery. First, carbosilane dendrons of second and third generation possessing ammonium or tertiary amine groups as peripheral functional groups were prepared. Hence, different strategies were tested in order to obtain their suitable grafting on the outer surface of the nanoparticles. As nucleic acid model, a single‐stranded DNA oligonucleotide tagged with a fluorescent Cy3 moiety was used to evaluate the DNA adsorption capacity. The hybrid material functionalised with the third generation of a neutral dendron showed excellent DNA binding properties. Finally, the cytotoxicity as well as the capability to deliver DNA into cells, was tested in vitro by using a human osteoblast‐like cell line, achieving good levels of internalisation of the vector DNA/carbosilane dendron‐functionalised material without affecting the cellular viability.     

Leaf‐Critical and Leaf‐Stable Graphs

The minimum leaf number ml(G) of a connected graph G is defined as the minimum number of leaves of the spanning trees of G if G is not hamiltonian and 1 if G is hamiltonian. We study nonhamiltonian graphs with the property for each or for each . These graphs will be called ‐leaf‐critical and l‐leaf‐stable, respectively. It is far from obvious whether such graphs exist; for example, the existence of 3‐leaf‐critical graphs (that turn out to be the so‐called hypotraceable graphs) was an open problem until 1975. We show that l‐leaf‐stable and l‐leaf‐critical graphs exist for every integer , moreover for n sufficiently large, planar l‐leaf‐stable and l‐leaf‐critical graphs exist on n vertices. We also characterize 2‐fragments of leaf‐critical graphs generalizing a lemma of Thomassen. As an application of some of the leaf‐critical graphs constructed, we settle an open problem of Gargano et al. concerning spanning spiders. We also explore connections with a family of graphs introduced by Grünbaum in correspondence with the problem of finding graphs without concurrent longest paths.     

Expression for the Number of Spanning Trees of Line Graphs of Arbitrary Connected Graphs

For any graph G, let be the number of spanning trees of G, be the line graph of G, and for any nonnegative integer r, be the graph obtained from G by replacing each edge e by a path of length connecting the two ends of e. In this article, we obtain an expression for in terms of spanning trees of G by a combinatorial approach. This result generalizes some known results on the relation between and and gives an explicit expression if G is of order and size in which s vertices are of degree 1 and the others are of degree k. Thus we prove a conjecture on for such a graph G.     

On the Minimum Number of Spanning Trees in k‐Edge‐Connected Graphs

We show that a k‐edge‐connected graph on n vertices has at least spanning trees. This bound is tight if k is even and the extremal graph is the n‐cycle with edge multiplicities . For k odd, however, there is a lower bound , where . Specifically, and . Not surprisingly, c₃ is smaller than the corresponding number for 4‐edge‐connected graphs. Examples show that . However, we have no examples of 5‐edge‐connected graphs with fewer spanning trees than the n‐cycle with all edge multiplicities (except one) equal to 3, which is almost 6‐regular. We have no examples of 5‐regular 5‐edge‐connected graphs with fewer than spanning trees, which is more than the corresponding number for 6‐regular 6‐edge‐connected graphs. The analogous surprising phenomenon occurs for each higher odd edge connectivity and regularity.     

Mathematical modelling and the learning trajectory: tools to support the teaching of linear algebra

In this article we present a didactic proposal for teaching linear algebra based on two compatible theoretical models: emergent models and mathematical modelling. This proposal begins with a problematic situation related to the creation and use of secure passwords, which leads students toward the construction of the concepts of spanning set and span. The objective is to evaluate this didactic proposal by determining the level of match between the hypothetical learning trajectory (HLT) designed in this study with the actual learning trajectory in the second experimental cycle of an investigation design-based research more extensive. The results show a high level of match between the trajectories in more than half of the conjectures, which gives evidence that the HLT has supported, in many cases, the achievement of the learning objective, and that additionally mathematical modelling contributes to the construction of these linear algebra concepts.     

Constructing near spanning trees with few local inspections

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let G be a connected bounded‐degree graph. Given an edge e in G we would like to decide whether e belongs to a connected subgraph consisting of edges (for a prespecified constant ), where the decision for different edges should be consistent with the same subgraph . Can this task be performed by inspecting only a constant number of edges in G ? Our main results are:

• We show that if every t‐vertex subgraph of G has expansion then one can (deterministically) construct a sparse spanning subgraph of G using few inspections. To this end we analyze a “local” version of a famous minimum‐weight spanning tree algorithm.
• We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of 3‐regular graphs of high girth, in which every t‐vertex subgraph has expansion . We prove that for this family of graphs, any local algorithm for the sparse spanning graph problem requires inspecting a number of edges which is proportional to the girth.

© 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 183–200, 2017     

超声全矩阵数据联合稀疏重构的多测量向量模型应用

针对单测量向量模型(Single Measurement Vector,SMV)等传统压缩感知方法处理超声全矩阵数据时,存在重构精度低和重构耗时长等问题,本文研究了多测量向量模型(Multiple Measurement Vectors,MMV)应用的可行性。针对铝合金试块中不同深度的φ2 mm横通孔,分别使用MMV模型中的多测量稀疏贝叶斯(Multiple Sparse Bayesian Learning,MSBL)算法和SMV模型中的稀疏贝叶斯(Sparse Bayesian Learning,SBL)算法进行超声全矩阵数据重构,并实施全聚焦成像。随后,引入归一化均方误差和阵列性能因子评价图像和信号的重构效果。实验结果表明,SBL算法在25%采样率时的归一化均方误差为1.9%,而MSBL算法仅需15%采样率即可达到相似效果且耗时更少。     

子结构Ritz向量综合法

讨论了在动态子结构法中应用静态Ｒｉｔｚ向量替代模态向量时所应考虑的基本问题，即如何合理地定义荷载空间分布向量｛ｆ（ｓ）｝，以避免在子结构中出现低阶模态不连续分布的情况。文中给出了在自由子结构和约束子结构内进行Ｒｉｔｚ变换的一般形式及修正公式。算例表明：应用子结构Ｒｉｔｚ向量综合技术能有效地提高线性结构模态分析的计算效率     

The number of spanning trees in an (r,s)‐semiregular graph and its line graph

For a graph G, a “spanning tree” in G is a tree that has the same vertex set as G. The number of spanning trees in a graph (network) G, denoted by t(G), is an important invariant of the graph (network) with lots of decisive applications in many disciplines. In the article by Sato (Discrete Math. 2007, 307, 237), the number of spanning trees in an (r, s)‐semiregular graph and its line graph are obtained. In this article, we give short proofs for the formulas without using zeta functions. Furthermore, by applying the formula that enumerates the number of spanning trees in the line graph of an (r, s)‐semiregular graph, we give a new proof of Cayley's Theorem. © 2013 Wiley Periodicals, Inc.