Factorizing the complete graph into factors with large star number

The graph G has star number n if any n vertices of G belong to a subgraph which is a star. Let f(n, k) be the smallest number m such that the complete graph on m vertices can be factorized into k factors with star number n. In the present paper we prove that $\text{c}{}_1{}^{\mathrm{n}}\text{k ≤ f(n, k) < c}{}_2{}^{\mathrm{n}}\text{k}$.     

On total matching numbers and total covering numbers of complementary graphs

Best upper and lower bounds, as functions of n, are obtained for the quantities $\text{β}{}_2\text{(G)+β}{}_2\text{(}\text{G}\text{?}\text{)}$ and $\text{α}{}_2\text{(G)+α}{}_2\text{(}\text{G}\text{?}\text{)}$, where β₂(G) denotes the total matching number and α₂(G) the total covering number of any graph G with n vertices and with complementry graph ?.The best upper bound is obtained also for α₂(G)+β₂(G), when G is a connected graph.     

Convex polyhedra of doubly stochastic matrices: II. Graph of Ωn

Properties of the graph $\text{G(Ω}{}_{\mathrm{n}}\text{)}$ of the polytope $\text{Ω}{}_{\mathrm{n}}$ of all n × n nonnegative doubly stochastic matrices are studied. If $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$ which is not a k-dimensional rectangular parallelotope for k ≥ 2, then G($\text{F}$) is Hamilton connected. Prime factor decompositions of the graphs of faces of $\text{Ω}{}_{\mathrm{n}}$ relative to Cartesian product are investigated. In particular, if $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$, then the number of prime graphs in any prime factor decomposition of G($\text{F}$) equals the number of connected components of the neighborhood of any vertex of G($\text{F}$). Distance properties of the graphs of faces of $\text{Ω}{}_{\mathrm{n}}$ are obtained. Faces $\text{F}$ of $\text{Ω}{}_{\mathrm{n}}$ for which G($\text{F}$) is a clique of $\text{G(Ω}{}_{\mathrm{n}}\text{)}$ are investigated.     

Convex polyhedra of doubly stochastic matrices. I. Applications of the permanent function

The permanent function is used to determine geometrical properties of the set $\text{Ω}{}_{\mathrm{n}}$ of all n × n nonnegative doubly stochastic matrices. If $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$, then $\text{F}$ corresponds to an n × n (0, 1)-matrix A, where the permanent of A is the number of vertices of $\text{F}$. If A is fully indecomposable, then the dimension of $\text{F}$ equals σ(A) ? 2n + 1, where σ(A) is the number of 1's in A. The only two-dimensional faces of $\text{Ω}{}_{\mathrm{n}}$ are triangles and rectangles. For n ? 6, $\text{Ω}{}_{\mathrm{n}}$ has four types of three-dimensional faces. The facets of the faces of $\text{Ω}{}_{\mathrm{n}}$ are characterized. Faces of $\text{Ω}{}_{\mathrm{n}}$ which are simplices are determined. If $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$ which is two-neighborly but not a simplex, then $\text{F}$ has dimension 4 and six vertices. All k-dimensional faces with k + 2 vertices are determined. The maximum number of vertices of a k-dimensional face is 2^k. All k-dimensional faces with at least 2^k?1 + 1 vertices are determined.     

Some Ramsey numbers for directed graphs

Given k directed graphs G₁,…,G_k the Ramsey number R(G₁,…, G_k) is the smallest integer n such that for any partition (U₁,…,U_k) of the arcs of the complete symmetric directed graph K_n, there exists an integer i such that the partial graph generated by U₁ contains G₁ as a subgraph. In the article we give a necessary and sufficient condition for the existence of Ramsey numbers, and, when they exist an upper bound function. We also give exact values for some classes of graphs. Our main result is: $\text{R(}\text{P}{}_{\mathrm{n}}\text{,….}\text{P}{}_{\mathrm{nk-1}}\text{, G) = n}{}_1\text{…n}{}_{\mathrm{k-1}}\text{(p-1) + 1}$, where G is a hamltonian directed graph with p vertices and $\text{P}{}_{\mathrm{n}}{}_{\mathrm{i}}$ denotes the directed path of length n_t     

Vertex degrees of planar graphs

Let G be a planar graph having n vertices with vertex degrees d₁, d₂,…,d_n. It is shown that $\text{Σ}{}_{\mathrm{i=1}}{}^{\mathrm{n}}\text{d}{}_{\mathrm{i}}{}^2\text{≤ 2n}{}^2\text{+ O(n)}$. The main term in this upper bound is best possible.     

On the maximum cardinality of a consistent set of arcs in a random tournament

For any tournament T on n vertices, let h(T) denote the maximum number of edges in the intersection of T with a transitive tournament on the same vertex set. Sharpening a previous result of Spencer, it is proved that, if T_n denotes the random tournament on n vertices, then, $\text{P}$$\text{(h(T}{}_{\mathrm{n}}\text{) ≤}\text{1}\text{2}\text{(}{}_2{}^{\mathrm{n}}\text{) + 1.73n}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}\text{) → 1}$ as n → ∞.     

Extremal uncrowded hypergraphs

Let G be a (k + 1)-graph (a hypergraph with each hyperedge of size k + 1) with n vertices and average degreee t. Assume k ? t ? n. If G is uncrowded (contains no cycle of size 2, 3, or 4) then there exists and independent set of size $\text{c}{}_{\mathrm{k}}\text{(}\text{n}\text{t}\text{)(}\text{ln}\text{t)}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}$.     

Parallel calculation of a linear mapping on a computer network

We are interested in the parallel computation of a linear mapping of n real variables by a network of computers with restricted means of communication between them and without any common memory. Let $\text{M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$ denote the algebra of n×n real matrices, and let G be the graph associated with a binary, reflexive and symmetric relation R over {1,2, …,n}. We define

$\text{A}{}_{\mathrm{R}}\text{= {A?M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{):a}{}_{\mathrm{ij}}\text{≠ 0}\text{implies}\text{iRj}}$

A matrix $\text{M∈M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$ is said to be realizable on G if it can be expressed as a product of elements of A_R. Therefore, every matrix of $\text{M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$ is realizable on G if and only if A_R generates $\text{M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$. We show that A_R generates $\text{M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$ if and only if G is connected.     

On the minimum order of graphs with given semigroup

Denote by M(n) the smallest positive integer such that for every n-element monoid M there is a graph G with at most M(n) vertices such that End(G) is isomorphic to M. It is proved that $\text{2}\text{(1 + o(1))n}\text{log}{}_2\text{n}\text{≤M(n)≤n ·}\text{2n}\text{+ O(n)}$. Moreover, for almost all n-element monoids M there is a graph G with at most 12 · n · log₂n + n vertices such that End(G) is isomorphic to M.     

Results on the edge-connectivity of graphs

It is shown that if G is a graph of order p ≥ 2 such that deg u + deg v ≥ p ? 1 for all pairs u, v of nonadjacent vertices, then the edge-connectivity of G equals the minimum degree of G. Furthermore, if deg u + deg v ≥ p for all pairs u, v of nonadjacent vertices, then either p is even and G is isomorphic to $\text{K}{}_{\mathrm{<mtext>p</mtext><mtext>2</mtext>}}\text{× K}{}_2$ or every minimum cutset of edges of G consists of the collection of edges incident with a vertex of least degree.     

Ramsey numbers for all linear forests

An (n, j) linear forest L is the disjoint union of nontrivial paths, such that j of the paths have an odd number of vertices and the union has n vertices. For L, an (n₁.j₁) linear forest and l₂ an (n.j₁) linear forest, we show that

$\text{r(L}{}_1\text{,L}{}_2\text{) = max{n}{}_1\text{·(n}{}_2\text{?j}{}_2\text{)/2 ? 1, n}{}_2\text{+ (n}{}_1\text{? j}{}_1\text{)/2 ? 1}.}$

This answers in the affirmative a conjecture of Burr and Roberts.     

A multiplication of distributions

If Ω denotes an open subset of $\text{R}$ⁿ (n = 1, 2,…), we define an algebra $\text{g}$ (Ω) which contains the space $\text{D}$′(Ω) of all distributions on Ω and such that $\text{C}{}^{\mathrm{\infty }}\text{(Ω)}$ is a subalgebra of $\text{G}$ (Ω). The elements of $\text{G}$ (Ω) may be considered as “generalized functions” on Ω and they admit partial derivatives at any order that generalize exactly the derivation of distributions. The multiplication in $\text{G}$(Ω) gives therefore a natural meaning to any product of distributions, and we explain how these results agree with remarks of Schwartz on difficulties concerning a multiplication of distributions. More generally if q = 1, 2,…, and $\text{?∈O}{}_{\mathrm{M}}\text{(}\text{R}{}^{\mathrm{2q}}\text{)}$—a classical Schwartz notation—for any G₁,…,G_q∈G(σ), we define naturally an element $\text{?G}{}_1\text{,…,G}{}_{\mathrm{q}}\text{∈G(σ)}$. These results are applied to some differential equations and extended to the vector valued case, which allows the multiplication of vector valued distributions of physics.     

The KMS condition and spectral passivity in group duality

Let (A, G, α) be a C¹-dynamical system, where G is abelian, and let φ be an invariant state. Suppose that there is a neighbourhood Ω of the identity in $\text{G}\text{?}$ and a finite constant κ such that $\text{Π}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{n}}\text{φ(x}{}_{\mathrm{i}}{}^1\text{x}{}_{\mathrm{i}}\text{) ? κ}\text{Π}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{n}}\text{φ(x}{}_{\mathrm{i}}\text{x}{}_{\mathrm{i}}{}^1\text{)}$ whenever x_i lies in a spectral subspace $\text{R}{}^{\mathrm{\alpha }}\text{(Ω}{}_{\mathrm{i}}\text{)}$, where $\text{Ω}{}_1\text{+ … + Ω}{}_{\mathrm{n}}\text{? Ω}$. This condition of complete spectral passivity, together with self-adjointness of the left kernel of φ, ensures that φ satisfies the KMS condition for some one-parameter subgroup of G.     

On the asymptotic number of tournament score sequences

An n-tournament is a complete labelled digraph on n vertices without loops or multiple arcs. A tournament's score sequence is the sequence of the out-degrees of its vertices arranged in nondecreasing order. The number S_n of distinct score sequences arising from all possible n-tournaments, as well as certain generalizations are investigated. A lower bound of the form

$\text{S}{}_{\mathrm{n}}\text{>}\text{C}{}_1\text{4}{}^{\mathrm{n}}\text{n}{}^{\mathrm{<mtext>5</mtext><mtext>2</mtext>}}$

(C₁ a constant) and an upper bound of the form $\text{S}{}_{\mathrm{n}}\text{<}\text{C}{}_2\text{4}{}^{\mathrm{n}}\text{n}{}^2$ are proved. A q-extension of the Catalan numbers

$\text{c}{}_1\text{(q)=1}\text{and}\text{c}{}_{\mathrm{n}}\text{(q)=}\text{∑}\text{i?1}\text{n?1}\text{c}{}_{\mathrm{i}}\text{(q)c}{}_{\mathrm{n?1}}\text{(q)q}{}^{\mathrm{i(n?i?1)}}$

is defined. It is conjectured that all coefficients in the polynomial C_n(q) are at most $\text{O(}\text{4}{}^{\mathrm{n}}\text{n}{}^3\text{)}$. It is shown that if this conjecture is true, then

$\text{S}{}_{\mathrm{n}}\text{<}\text{C}{}_3\text{4}{}^{\mathrm{n}}\text{n}{}^{\mathrm{<mtext>5</mtext><mtext>2</mtext>}}$

     

Elementary proof of the transformation formula for Lambert series involving generalized Dedekind sums

An elementary proof is given of the author's transformation formula for the Lambert series $\text{G}{}_{\mathrm{p}}\text{(x) =}\text{Σ}{}_{\mathrm{n?1}}{}^{\mathrm{<mtext>\infty </mtext>}}\text{n}{}^{\mathrm{?p}}\text{x}{}^{\mathrm{n}}\text{(1?x}{}^{\mathrm{n}}\text{)}$ relating G_p(e^2πiτ) to G_p(e^2πiAτ), where p > 1 is an odd integer and $\text{Aτ =}\text{(aτ + b)}\text{(cτ + d)}$ is a general modular substitution. The method extends Sczech's argument for treating Dedekind's function $\text{log}\text{η(τ) =}\text{πiτ}\text{12}\text{? G}{}_1\text{(e}{}^{\mathrm{2\pi i\tau }}\text{)}$, and uses Carlitz's formula expressing generalized Dedekind sums in terms of Eulerian functions.     

Bounds on path connectivity

The path-connectivity of a graph G is the maximal k for which between any k pairs of vertices there are k edge-disjoint paths (one between each pair). An upper bound for the path-connectivity of n^q(q<1) separable graphs [6] is shown to exist.If the edge-connectivity of a graph is K_E then between any two pairs of vertices and for every $\text{t?}\text{K}{}_{\mathrm{E}}$ there exists a t?t′?t+1 such that there are t′ paths between the first pair and $\text{K}{}_{\mathrm{E}}\text{?t′}$ between the second pair. All paths are edge-disjoint.     

An upper bound on the path number of a digraph

A proof is presented of the conjecture of Alspach and Pullman that for any digraph G on n ≥ 4 vertices, the path number of G is at most [$\text{n}{}^2\text{4}$].