SOME COMBINATORIAL PROBLEMS ON ORDERED TREES

Some formulas are established to calculate the number of leaves on all structurallydifferent ordered trees with n nodes,and the total leaf path length and the total node pathlength for those trees.Certainly,respective average numbers are obtained(the average pathlength may be considered as the average height of random ordered trees with n nodes),Actually,this paper presents a general method dealing with some classes of combinaorialproblems on ordered trees.     

Bipartite Version of the Erd?s-Sós Conjecture

The Erd?s-Sós Conjecture states that every graph on n vertices and more than n(k-2)/2 edges contains every tree of order k as a subgraph. In this note, we study a weak(bipartite)version of Erd?s-Sós Conjecture. Based on a basic lemma, we show that every bipartite graph on n vertices and more than n(k-2)/2 edges contains the following families of trees of order k:(1) trees of diameter at most five;(2) trees with maximum degree at least [k-1/2];(3) almost balanced trees, these results are better than the corresponding known results for the general version of the Erd?s-Sós Conjecture.     

Enumeration of rooted nonseparable outerplanar maps

In this paper, the number of combinatorially distinct rooted nonseparable outerplanar maps withm edges and the valency of the root-face being n is found to be(m-1)! (m-2) !:(n-1)!(n-2)! (m-n)!(m-n 1)!and, the number of rooted nonseparable outerplanar maps with m edges is also determined to be(2m-2)!:(m-1)!m!,which is just the number of distinct rooted plane trees with m-1 edges.     

A variation of a conjecture due to Erdös and Sós

Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e（G） 〉 1/2（k - 1）n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 ＋ 37/2＋ 14 and every graph G on n vertices with e（G） 〉 1/2 （k- 1）n, we prove that there exists a graph G＇ on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.     

AN ENUMERATION PROBLEM ON t-ARY TREES

In this paper, an enumeration problem on t-ary trees with m interior nodes and n leaves is discussed. In the analysis of algorithms over tree structures, it is not sufficient to consider roughly the behavior of algorithms over trees with m nodes, because the difference between the structures of the two different trees with m nodes may be great. However, on the other hand, the difference between the structures of the trees with m interior nodes and n leaves may be relatively small. Thus, in such an analysis, it is needed to count the number of struc-     

ON NODE ENUMERATION AND NODE PATH LENGTH OF ORDERED TREES

Considering the class (n, m) of ordered trees with m leaves and n-m internal nodes, a set of generating functions are established for the following problems: (1) the total number nodes with degree r over Γ(n, m), (2) the total path length of nodes over Γ(n, m), and (3) the total number of nodes over Γ(n, m) on level k. Some particular counting fomulas are derived from them.     

On the maximal eccentric connectivity indices of graphs

For a connected simple graph G, the eccentricity ec(v) of a vertex v in G is the distance from v to a vertex farthest from v, and d(v) denotes the degree of a vertex v. The eccentric connectivity index of G, denoted by ξc(G), is defined as v∈V(G)d(v)ec(v). In this paper, we will determine the graphs with maximal eccentric connectivity index among the connected graphs with n vertices and m edges(n ≤ m ≤ n + 4), and propose a conjecture on the graphs with maximal eccentric connectivity index among the connected graphs with n vertices and m edges(m ≥ n + 5).     

关于完全二部图$K_{4, n}$和$K_{n, n}$的点可区别 $IE$-全染色的一些注记

Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article.     

Transitivity of varietal hypercube networks

The varietal hypercube VQn is a variant of the hypercube Qn and has better properties than Qn with the same number of edges and vertices. This paper proves that VQn is vertex-transitive. This property shows that when VQn is used to model an interconnection network, it is high symmetrical and obviously superior to other variants of the hypercube such as the crossed cube.     

The backup 2-median problem on block graphs

The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O（n log n q- m）-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph.     

Protected Branches in Ordered Trees

In this paper, we consider the class of ordered trees and its two subclasses, bushes and planted trees, which consist of the ordered trees with root degree at least $2$ and with root degree $1$ respectively. In these three classes, we study the number of trees of size $n$ with $k$ protected (resp. unprotected) branches, and the total number of branches (resp. protected branches, unprotected branches) among all trees of size $n$. The explicit formulas as well as the generating functions are obtained. Furthermore, we find that, in each class, as $n$ goes to infinity, the proportion of protected branches among all branches in all trees of size $n$ approaches $ 1/3$.     

二部图形式的Erd\H{O}s-S\'{o}s猜想

二部图形式的Erd\H{O}s-S\''{o}s猜想     

图的平面Turán数和平面anti-Ramsey数

在所有顶点数为$n$且不包含图$G$作为子图的平面图中,具有最多边数的图的边数称为图$G$的平面Turán数,记为$ex_{_\mathcal{P}}（n,G）$。给定正整数$n$以及平面图$H$,用$\mathcal{T}_n （H）$来表示所有顶点数为$n$且不包含$H$作为子图的平面三角剖分图所组成的图集合。设图集合$\mathcal{T}_n （H）$中的任意平面三角剖分图的任意$k$边染色都不包含彩虹子图$H$,则称满足上述条件的$k$的最大值为图$H$的平面anti-Ramsey数,记作$ar_{_\mathcal{P}}（n,H）$。两类问题的研究均始于2015年左右,至今已经引起了广泛关注。全面地综述两类问题的主要研究成果,以及一些公开问题。     

关于双圈图的谱半径

如果G是连通的并且G的边数是n 1,那么n阶图G叫做双圈图,设B(n)是所有的阶为n的双圈图构成的集合,本文给出了B(n)(n(?)9)中前三大的邻接谱半径以及它们对应的图.     

Relative locations of subwords in free operated semigroups and Motzkin words

Bracketed words are basic structures both in mathematics (such as Rota-Baxter algebras) and mathematical physics (such as rooted trees) where the locations of the substructures are important. In this paper, we give the classification of the relative locations of two bracketed subwords of a bracketed word in an operated semigroup into the separated, nested, and intersecting cases. We achieve this by establishing a correspondence between relative locations of bracketed words and those of words by applying the concept of Motzkin words which are the algebraic forms of Motzkin paths.     

关于三圈图的拉普拉斯谱半径的一些结果

边数等于点数加二的连通图称为三圈图.~设 ~$\Delta(G)$~和~$\mu(G)$~
分别表示图~$G$~的最大度和其拉普拉斯谱半径,设${\mathcal
T}(n)$~表示所有~$n$~阶三圈图的集合,证明了对于~${\mathcal
T}(n)$~的两个图~$H_{1}$~和~$H_{2}$~,~若~$\Delta(H_{1})>
\Delta(H_{2})$ ~且 ~$\Delta(H_{1})\geq \frac{n+7}{2}$,~则~$\mu
(H_{1})> \mu (H_{2}).$ 作为该结论的应用,~确定了~${\mathcal
T}(n)(n\geq9)$~中图的第七大至第十九大的拉普拉斯谱半径及其相应的极图.     

具有第二大基指数的本原对称带号有向图的刻画

Recently, the primitive symmetric signed digraphs on n vertices with the maximum base 2n and the primitive symmetric loop-free signed digraphs on n vertices with the maximum base 2n-1 are characterized, respectively. In this paper, the primitive symmetric signed digraphs with loops on n vertices with the base 2n-1 are characterized, and then the primitive symmetric signed digraphs on n vertices with the second maximum base 2n-1 are characterized.     

通过增强型萨格勒布指数对图排序

Recently, Furtula et al. proposed a valuable predictive index in the study of the heat of formation in octanes and heptanes, the augmented Zagreb index(AZI index) of a graph G, which is defined as AZI(G) =∑uv∈E(G)( d_u d_v/d_u + d_v-2)~3,where E(G) is the edge set of G, d u and d v are the degrees of the terminal vertices u and v of edge uv, respectively. In this paper, we obtain the first five largest(resp., the first two smallest) AZI indices of connected graphs with n vertices. Moreover, we determine the trees of order n with the first three smallest AZI indices, the unicyclic graphs of order n with the minimum, the second minimum AZI indices, and the bicyclic graphs of order n with the minimum AZI index, respectively.     

$K_{2,3}$的剖分图与$P_n, C_n$的联图交叉数

在完全图$K_{2,3}$的任意一边增加一个新的顶点, 则得到$K_{2,3}$的一个剖分图(六阶图). 本文研究得到了这个特殊六阶图与$n$个孤立点$nK_1$, 路$P_n$, 圈$C_n$的联图交叉数.     

An edge-swap heuristic for generating spanning trees with minimum number of branch vertices

This paper presents a new edge-swap heuristic for generating spanning trees with a minimum number of branch vertices, i.e. vertices of degree greater than two. This problem was introduced in Gargano et al. (Lect Notes Comput Sci 2380:355–365, 2002) and has been called the minimum branch vertices problem by Cerulli et al. (Comput Optim Appl 42:353–370, 2009). The heuristic starts with a random spanning tree and iteratively reduces the number of branch vertices by swapping tree edges with edges not currently in the tree. It can be easily implemented as a multi-start heuristic. We report on extensive computational experiments comparing single-start and multi-start variants on our heuristic with other heuristics previously proposed in the literature.