Characterizations of maximum matching graphs of certain types

The maximum matching graph of a graph G is a graph whose vertices are maximum matchings of G and where two maximum matchings are adjacent in if they differ in exactly one edge. In this paper, the author characterizes the graphs whose maximum matching graphs are regular or cycles, and adds trees to the list of known maximum matching graphs.     

The problem of the time-optimal turning of a manipulator

Two types of manipulator that perform three-dimensional motions are considered, and the control problem in which the manipulator rotation is performed in minimum time is studied. The rate of rotation of a rigid body about an axis rises as the moment of inertia about this axis falls. Manipulator control amounts to a problem of the rotation of a system of rigid bodies about an axis. In addition to the angle of rotation, there is a further controlled coordinate, whose variation can vary the moment of inertia about the axis. Assuming that the moment of inertia can be stantaneously “frozen” (that pulse control signals are possible), the in-time-optimal control modes were found in /1, 2/, (see also Akulenko, L.D. et al., “Optimization of the control modes of manipulation robots”, Preprint 218, In-t. Problem Mekhaniki Akad. Nauk SSSR, Moscow 1983). In these modes, the rotation, occurs in the entire time interval with minimum moment of inertia about the axis of rotation. The rotation when there are constraints on the control (pulse control signals are not permitted) was considered in /3/. Numerical studies there led to the false conclusion that, in the optimal motion, with a finite number of control switchings, the moment of inertia is also a minimum throughout the time interval. Below, for a set of extreme configurations, a control is constructed for the two types of manipulator, which satisfies the Pontryagin maximum principle, when there are constraints on the control signals. During its rotation the manipulator section then performs oscillations about a position corresponding to minimum moment of inertia about the axis of rotation. It is shown that the motion considered in /3/, which contains a singular mode with minimum moment of inertia, is not optimal. The motion which satisfies the maximum principle is compared with it. There can be a singular mode in the optimal motion /4/ only when the number of control switchings is infinite.     

3-一致超图的反馈数研究

超图H=(V,E)顶点集为V,边集为E.S■V是H的顶点子集,如果H/S不含有圈,则称S是H的点反馈数,记τc(H)是H的最小点反馈数.本文证明了:(i)如果H是线性3-一致超图,边数为m,则τc(H)≤m/3;(ii)如果H是3-一致超图,边数为m,则τc(H)≤m/2并且等式成立当且仅当H任何一个连通分支是孤立顶点或者长度为2的圈.A■V是H的边子集,如果H\A不含有圈,则称A是H的边反馈数,记τc′(H)是H的最小边反馈数.本文证明了如果H是含有p个连通分支的3-一致超图,则τc’(H)≤2m-n+p.     

A note on line coverings of graphs

Let minimum, maximum, refer to the number of elements in a set and let minimal, maximal refer to set inclusion. It is shown that a minimal cover of a graph is minimum if and only if it contains a maximum matching of that graph; a maximal matching of a graph is maximum if and only if it is contained in a minimum cover of that graph diminished by the set of its isolated points.     

Induced Matching Number of the Plane Grid Graph

An induced matching M in a graph G is a matching such that V(M) induces a 1-regular subgraph of G. The induced matching number of a graph G, denoted by I M(G), is the maximum number r such that G has an induced matching of r edges. Induced matching number of Pm×Pn is investigated in this paper. The main results are as follows:(1) If at least one of m and n is even, then IM(Pm×Pn=[(mn)/4].(2) If m is odd, then     

INDEPENDENT-SET-DELETABLE FACTOR-CRITICAL POWER GRAPHS

It is said that a graph G is independent-set-deletable factor-critical (in short, ID-factor-critical), if, for every independent set 7 which has the same parity as |V(G)|, G-I has a perfect matching. A graph G is strongly IM-extendable, if for every spanning supergraph H of G, every induced matching of H is included in a perfect matching of H. The k-th power of G, denoted by Gk, is the graph with vertex set V(G) in which two vertices are adjacent if and only if they have distance at most k in G. ID-factor-criticality and IM-extendability of power graphs are discussed in this article. The author shows that, if G is a connected graph, then G3 and T(G) (the total graph of G) are ID-factor-critical, and G4 (when |V(G)| is even) is strongly IM-extendable; if G is 2-connected, then D2 is ID-factor-critical.     

A bound on judicious bipartitions of directed graphs

Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously,which have received much attention lately.Scott(2005)asked the following natural question:What is the maximum constant cdsuch that every directed graph D with m arcs and minimum outdegree d admits a bipartition V(D)=V_1∪V_2 satisfying min{e(V_1,V_2),e(V_2,V_1)}cdm?Here,for i=1,2,e(V_i,V_3-i)denotes the number of arcs in D from V_i to V_3-i.Lee et al.(2016)conjectured that every directed graph D with m arcs and minimum outdegree at least d 2 admits a bipartition V(D)=V_1∪V_2 such that min{e(V_1,V_2),e(V_2,V_1)}≥((d-1)/(2(2 d-1))+o(1))m.In this paper,we show that this conjecture holds under the additional natural condition that the minimum indegree is also at least d.     

不同规模单水平样本轮换最优轮换率的确定

在单水平样本轮换抽样调查中,我们假设每期调查的规模不一定相等,分别在给定总的费用和给定精度要求的条件下,求出了使得估计量的方差达到最小的最优轮换率以及最优样本容量。     

Total matchings and total coverings of graphs

In graph theory, the related problems of deciding when a set of vertices or a set of edges constitutes a maximum matching or a minimum covering have been extensively studied. In this paper we generalize these ideas by defining total matchings and total coverings, and show that these sets, whose elements in general consist of both vertices and edges, provide a way to unify these concepts. Parameters denoting the maximum and the minimum cardinality of these sets are introduced and upper and lower bounds depending only on the order of the graph are obtained for the number of elements in arbitrary total matchings and total coverings. Precise values of all the parameters are found for several general classes of graphs, and these are used to establish the sharpness of most of the bounds. In addition, variations of some well known equalities due to Gallai relating covering and matching numbers are obtained.     

Limit laws for the maximum and minimum of stationary sequences

Summary The class of non-degenerate joint limiting distributions for the maximum and minimum of stationary mixing sequences is determined. These limit distributions are of the form, H(x, ) –H(x, –y), where H(x,y) is a bivariate extreme value distribution. Unlike the classical result for i.i.d. sequences, the maximum and minimum of stationary mixing sequences may be asymptotically dependent. We also give a sufficient condition for the asymptotic independence of the maximum and minimum. Finally, an example of a stationary sequence satisfying the mixing condition D in Leadbetter but which is not weakly mixing is constructed.This research was supported in part by the National Science Foundation grant MCS 80-05483     

A short proof of König's matching theorem

We give a short proof of the following basic fact in matching theory: in a bipartite graph the maximum size of a matching equals the minimum size of a node cover. © John Wiley & Sons, Inc. J Graph Theory 33: 138–139, 2000     

DEGREE CONDITIONS OF INDUCED MATCHING EXTENDABLE GRAPHS

Abstract. A simple graph G is induced matching extendable,shortly IM-extendable,if every in-duced matching of G is included in a perfect matching of G. The degree conditions of IM-extend-able graphs are researched in this paper. The main results are as follows：     

An annulus diffeomorphism with non-Denjoy minimal sets

We construct an annulus diffeomorphism with the property that a countably dense set of irrational rotation numbers are represented only by pseudocircles on which the diffeomorphism acts minimally but is not semi-conjugate to rigid rotation on the circle. This answers a question of Boyland about whether such behavior is possible only at the maximum or minimum of the rotation set.

     

On matching and total domination in graphs

A set M of edges of a graph G is a matching if no two edges in M are incident to the same vertex. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The matching number is the maximum cardinality of a matching of G, while the total domination number of G is the minimum cardinality of a total dominating set of G. In this paper, we investigate the relationships between the matching and total domination number of a graph. We observe that the total domination number of every claw-free graph with minimum degree at least three is bounded above by its matching number, and we show that every k-regular graph with k?3 has total domination number at most its matching number. In general, we show that no minimum degree is sufficient to guarantee that the matching number and total domination number are comparable.     

Imprimitive matrices of zeros and ones with extremal numbers of ones

In [X. Zhan, Extremal numbers of positive entries of imprimitive nonnegative matrices, Linear Algebra Appl. 424 (2007) 132–138], Zhan determined the maximum and minimum numbers of positive entries of irreducible nonnegative matrices. In this paper, we characterize the irreducible (0,1) matrices with the maximum and minimum numbers of positive entries.     

Maximum genus, connectivity and minimal degree of graphs

This paper is devoted to the lower bounds on the maximum genus of graphs. A simple statement of our results in this paper can be expressed in the following form:

Let G be a k-edge-connected graph with minimum degree δ, for each positive integer k(3), there exists a non-decreasing function f(δ) such that the maximum genus γ_M(G) of G satisfies the relation γ_M(G)f(δ)β(G), and furthermore that lim_δ→∞f(δ)=1/2, where β(G)=|E(G)|-|V(G)|+1 is the cycle rank of G.

The result shows that lower bounds of the maximum genus of graphs with any given connectivity become larger and larger as their minimum degree increases, and complements recent results of several authors.     

立方图的对控制数

设G=(V,E)是一个简单图, 对任意的顶点子集合 $S\subseteq V$, G[S]表示图G中由S所导出的子图. 如果S是G的一个控制集并且G[S]包含至少一个完备匹配, 则称S是G的一个对控制集. G中对控制集的最少的顶点数称为$G$的对控制数, 记为γ_p(G). 该文证明了对任意有n点的连通立方图G, γ_p(G)≤3n/ 5.     

退化图中的子图计数问题研究

令G表示n个顶点的图,如果G的每个子图中都包含一个度至多为k的顶点,则称G为k-退化图.令N(G,F)表示G中F子图的个数.主要研究了k-退化图中完全子图和完全二部子图的计数问题,给出了计数的上界以及相应的极图.首先,证明了Ν(G,K_t)≤(n-k)(k t-1)+(k t).其次,如果s,t≥1,n≥k+1且s+t≤k,我们证明了Ν(G,K_s,t)≤{(k s)(n-s s)-1/2(k s)(k-s s),t=s,(k s)(n-s t)+(k t)(n-t s)-(k t)(k-t s),t≠s.此外,还研究了在最大匹配和最小点覆盖为给定值的情况下,图G中的最大边数.记v(G),K(G)分别为图G的最大匹配数和最小点覆盖.证明了当v(G)≤k,K(G)=k+r且n≥2k+2r²+r+1时,有e(G)≤(k+r+1 2)+(k-r)(n-k-r-1).