Eccentric graphs

For any graph G we define the eccentric graph G_e on the same set of vertices, by joining two vertices in G_e if and only if one of the vertices has maximum possible distance from the other. The following results are given in this paper:

• (1)A few general properties of eccentric graphs.
• (2)A characterization of graphs G with G_e = K_p and with G_e = pK₂.
• (3)A solution of the equation G_e = G¯.

     

A spectral approach to polyhedral dimension

Thespectrum spec( ) of a convex polytope is defined as the ordered (non-increasing) list of squared singular values of [A|1], where the rows ofA are the extreme points of . The number of non-zeros in spec( ) exceeds the dimension of by one. Hence, the dimension of a polytope can be established by determining its spectrum. Indeed, this provides a new method for establishing the dimension of a polytope, as the spectrum of a polytope can be established without appealing to a direct proof of its dimension. The spectrum is determined for the four families of polytopes defined as the convex hulls of:

1. The edge-incidence vectors of cutsets induced by balanced bipartitions of the vertices in the complete undirected graph on 2_q vertices (see Section 6).
2. The edge-incidence vectors of Hamiltonian tours in the complete undirected graph onn vertices (see Section 6).
3. The arc-incidence vectors of directed Hamiltonian tours in the complete directed graph ofn nodes (see Section 7).
4. The edge-incidence vectors of perfect matchings in the complete 3-uniform hypergraph on 3_q vertices (see Section 8).

In the cases of (ii) and (iii), the associated dimension results are well-known. The dimension results for (i) and (iv) do not seem to be well-known. General principles are discussed for ‘balanced polytopes’ arising from complete structures.     

An optimal time to sleep for an auto-sleep system considering multi-usage states

An auto-sleep system is defined by the following two properties:

• 1.(i) a call for the system occurs randomly and intermittently
• 2.(ii) the system automatically goes to sleep if there occurs no call during a prespecified time T.

It considers four states:

• 1.(a) sleep
• 2.(b) warm-up
• 3.(c) nonusage
• 4.(d) usage.

For such a system, the time to sleep has been discussed based on suitable criteria. This study extends the model for an auto-sleep system so that the model can deal with multi-usage states. With a view to determining an optimal time to sleep under the extended model, the expected energy consumed per unit time is formulated as a criterion to be minimized. The existence of an optimal time to sleep is examined under a general call distribution. Numerical examples are also provided for a Weibull as well as a log-normal call distribution.     

Spectral radius of <Emphasis Type="Italic">r</Emphasis>-uniform supertrees with perfect matchings

supertree is a connected and acyclic hypergraph. The set of r-uniform supertrees with n vertices and the set of r-uniform supertrees with perfect matchings on rk vertices are denoted by T_n and T_r,k, respectively. H. Li, J. Shao, and L. Qi [J. Comb. Optim., 2016, 32(3): 741–764] proved that the hyperstar S_n,r attains uniquely the maximum spectral radius in T_n. Focusing on the spectral radius in T_r,k, this paper will give the maximum value in T_r,k and their corresponding supertree.     

A decomposition of the Brownian path

The Brownian path {ω(s); 0 ⩽ s ⩽ t} is dissected and then reassembled in such a way that

• (i) the last visit γ_t at the origin, as well as the fragment {ω(s); γ_t ⩽ s ⩽ t}, are left invariant;
• (ii) on [0, γ_t], local time becomes maximum-to-date and occupation time of|R₊ becomes location of maximum; and
• (iii) the resulting process is again Brownian.

Characterizations of conditional processes are employed to establish the result. Several consequences of the latter are discussed.     

A Note on Old Babylonian Computational Techniques

Analysis of the errors in two Old Babylonian “algebraic” problems shows

• •that the computations were performed on a device where additive contributions were no longer identifiable once they had entered the computation;
• •that this device must have been some kind of counting board or abacus where numbers were represented as collections of calculi;
• •that units and tens were represented in distinct ways, perhaps by means of different calculi.

© 2002 Elsevier Science (USA).Eine Analyse der Rechenfehler in zwei altbabylonischen “algebraischen” Aufgaben läßt mehrere Rückschlüsse auf ein Hilfsmittel zu, das zur Durchführung von Rechnungen benutzt worden sein kann:

• •Additive Beiträge waren nach ihrer Eintragung in die Rechnung nicht länger identifizierbar.
• •Das Gerät war eine Art Rechenbrett, auf welchem Zahlen als Haufen von Rechensteinen erschienen.
• •Einer und Zehner wurden in verschiedener Weise, evtl. mittels verschiedener Rechensteine repräsentiert.

© 2002 Elsevier Science (USA).MSC subject classification: 01A17.     

On degree sequences of undirected,directed, and bidirected graphs

Bidirected graphs generalize directed and undirected graphs in that edges are oriented locally at every node. The natural notion of the degree of a node that takes into account (local) orientations is that of net-degree. In this paper, we extend the following four topics from (un)directed graphs to bidirected graphs:

• –Erdős–Gallai-type results: characterization of net-degree sequences,
• –Havel–Hakimi-type results: complete sets of degree-preserving operations,
• –Extremal degree sequences: characterization of uniquely realizable sequences, and
• –Enumerative aspects: counting formulas for net-degree sequences.

To underline the similarities and differences to their (un)directed counterparts, we briefly survey the undirected setting and we give a thorough account for digraphs with an emphasis on the discrete geometry of degree sequences. In particular, we determine the tight and uniquely realizable degree sequences for directed graphs.     

Laplacian Spectral Radius and Maximum Degree of Trees with Perfect Matchings

Let μ(T) and Δ(T) denote the Laplacian spectral radius and the maximum degree of a tree T, respectively. Denote by ${\mathcal{T}_{2m}}$ the set of trees with perfect matchings on 2m vertices. In this paper, we show that for any ${T_1, T_2\in\mathcal{T}_{2m}}$ , if Δ(T ₁) > Δ(T ₂) and ${\Delta(T_1)\geq \lceil\frac{m}{2}\rceil+2}$ , then μ(T ₁) > μ(T ₂). By using this result, the first 20th largest trees in ${\mathcal{T}_{2m}}$ according to their Laplacian spectral radius are ordered. We also characterize the tree which alone minimizes (resp., maximizes) the Laplacian spectral radius among all the trees in ${\mathcal{T}_{2m}}$ with an arbitrary fixed maximum degree c (resp., when ${c \geq \lceil\frac{m}{2}\rceil + 1}$ ).     

Constructing a perfect matching is in random NC

We show that the problem of constructing a perfect matching in a graph is in the complexity class Random NC; i.e., the problem is solvable in polylog time by a randomized parallel algorithm using a polynomial-bounded number of processors. We also show that several related problems lie in Random NC. These include:

1. Constructing a perfect matching of maximum weight in a graph whose edge weights are given in unary notation;
2. Constructing a maximum-cardinality matching;
3. Constructing a matching covering a set of vertices of maximum weight in a graph whose vertex weights are given in binary;
4. Constructing a maximums-t flow in a directed graph whose edge weights are given in unary.

     

Survey of mathematical programming models in air pollution management

This paper surveys the current state of the literature in management science/operations research approaches to air pollution management. After introducing suitable background we provide some of the institutional and legal framework needed to understand the continuing regulatory efforts in United States. Attention is then turned to mathematical programming models ranging from fairly simple deterministic linear programs to quite sophisticated stochastic models which have appeared in the literature dealing with these topics. This is followed by extensions reflecting some of the work we have undertaken in association with the Texas Natural Resource Conservation Commission, a regulatory agency in Texas. Application and potential use of models is the central theme of this survey. Issues for future research are presented at the end and an extensive list of publications is provided in the references at the end of the article.Principal air quality issues of local, national, and international concern are listed below in increasing order of difficulty based on the number of different types of pollutants and problems in quantification of the risks the pollutants pose:

• 1.1. Stratospheric ozone depletion: one relatively easily controllable class of trace gases - ozone depleting chemicals, or ODCs, principally chloroflurocarbons (CFCs) — with relatively well quantified risks;
• 2.2. Criteria pollutants: six common pollutants — ozone (O₃), carbon monoxide (CO), sulfur dioxide (SO₂), nitrogen dioxide (NO₂), lead (Pb), and particulate matter less than 10 microns in size (PM10) — regulated since 1970 in the U.S. and presenting relatively well quantified risks;
• 3.3. Acid precipitation: two relatively easily controllable classes of trace gases — oxides of nitrogen (NO_x) and oxides of sulfur (SO_x) with relatively well quantified risks;
• 4.4. Global warming/climate change: a few difficult to control trace gases — principally carbon dioxide (CO₂), methane (CH₄), nitrous oxide (N₂O), and CFCs — with highly uncertain risks;
• 5.5. Toxics or HAPS (hazardous air pollutants): hundreds of types of gaseous chemicals and particles with uncertain risks;
• 6.6. Somewhat dated, but nevertheless useful, is the following reference: Glossary on Air Pollution (Copenhagen, World Health Organization, 1980).

     

Weak isomorphism of measure-preserving diffeomorphisms

On the two-dimensional torus we construct twoC{∞}-diffeomorphismsT ₁,T ₂ satisfying:

1. T ₁,T ₂ preserve Lebesgue measure and are ergodic with respect to it,
2. T ₁,T ₂ are measurable factors of each other,
3. T ₁,T ₂ are not measure-theoretically isomorphic.

     

Drawing Trees with Perfect Angular Resolution and Polynomial Area

We study methods for drawing trees with perfect angular resolution, i.e., with angles at each node $v$ equal to $2\pi /d(v)$ . We show:

1. Any unordered tree has a crossing-free straight-line drawing with perfect angular resolution and polynomial area.
2. There are ordered trees that require exponential area for any crossing-free straight-line drawing having perfect angular resolution.
3. Any ordered tree has a crossing-free Lombardi-style drawing (where each edge is represented by a circular arc) with perfect angular resolution and polynomial area.

Thus, our results explore what is achievable with straight-line drawings and what more is achievable with Lombardi-style drawings, with respect to drawings of trees with perfect angular resolution.     

New families of graceful banana trees

Consider a family of stars. Take a new vertex. Join one end-vertex of each star to this new vertex. The tree so obtained is known as abanana tree. It is proved that the banana trees corresponding to the family of stars

1. (K_1,1, K_1,2,…, K_{1,t ?1}, (α + l) K_1,t, K_{1,t + 1}, …, K_1,n), α ? 0
2. (2K_1,1, 2K_1,2,…, 2K_{1,t? 1}, (α + 2)K_1,t, 2K_{1,t + 1, …}, 2K_1,n), 0 ? α <t and
3. (3K_1,t, 3K_1,2, …, 3K_1,n) are graceful.

     

Analysis of performance of an iron-bath reactor using computational fluid dynamics

The performance of an iron-bath reactor has been studied using a comprehensive numerical model that combines a computational fluid dynamics approach for the gas phase and a heat and mass balance model for the bath. The model calculates:

• •coal, ore, flux and oxygen consumption;
• •post-combustion ratio (PCR);
• •heat-transfer efficiency (HTE);
• •off-gas temperature and composition;
• •heat transfer and chemical reactions between gas and iron and slag droplets; and
• •heat transfer between gas and bath, refractories and lance.

The model was validated with data reported by the Nippon Steel Corporation for a 100 t pilot plant, and the calculated and measured data are in good agreement. Modelling results showed that the dominant mechanisms of heat transfer from the gas to the bath are radiation to the slag surface and convection heat transfer to droplets.     

Mathematical modelling of the flotation deinking process

The overall flotation deinking process can be divided into four basic microprocesses:

• 1.(1) collision or capture of an (ink) particle by an air bubble
• 2.(2) adhesion of an (ink) particle to the air bubble by sliding
• 3.(3) development of a three-phase contact at the air bubble/water/particle interface, and
• 4.(4) bubble/particle stability or instability after an aggregate is formed each of these microprocesses have an associated probability that they will occur successfully in a flotation cell.

In this paper, the associated probabilities of each microprocess are employed in the development of a kinetic- or population balance-type model of the overall flotation process. The overall model contains two kinetic constants: the first, k₁ governs the overall probability of a free ink particle successfully intercepting and adhering to an air bubble; the second, k₂ is a measure of the probability that a bubble/particle aggregate pair will become unstable and split to yield a “new” free ink particle.The solution to the kinetic model is presented in terms of k₁ and k₂, which are themselves functions of system parameters such as bubble and particle physical properties (e.g., diameter, density), fluid properties (e.g., viscosity, surface tension), etc. From this solution, a definition of a theoretical flotation efficiency, as well as other system performance parameters are presented.     

Compactness and the axiom of choice

In the absence of the axiom of choice four versions of compactness (A-, B-, C-, and D-compactness) are investigated. Typical results:

1. C-compact spaces form the epireflective hull in Haus of A-compact completely regular spaces.
2. Equivalent are:
3. the axiom of choice,
4. A-compactness = D-compactness,
5. B-compactness = D-compactness,
6. C-compactness = D-compactness and complete regularity,
7. products of spaces with finite topologies are A-compact,
8. products of A-compact spaces are A-compact,
9. products of D-compact spaces are D-compact,
10. powers X ^k of 2-point discrete spaces are D-compact,
11. finite products of D-compact spaces are D-compact,
12. finite coproducts of D-compact spaces are D-compact,
13. D-compact Hausdorff spaces form an epireflective subcategory of Haus,
14. spaces with finite topologies are D-compact.

1. Equivalent are:
2. the Boolean prime ideal theorem,
3. A-compactness = B-compactness,
4. A-compactness and complete regularity = C-compactness,
5. products of spaces with finite underlying sets are A-compact,
6. products of A-compact Hausdorff spaces are A-compact,
7. powers X ^k of 2-point discrete spaces are A-compact,
8. A-compact Hausdorff spaces form an epireflective subcategory of Haus.

1. Equivalent are:
2. either the axiom of choice holds or every ultrafilter is fixed,
3. products of B-compact spaces are B-compact.

1. Equivalent are:
2. Dedekind-finite sets are finite,
3. every set carries some D-compact Hausdorff topology,
4. every T ₁-space has a T ₁-D-compactification,
5. Alexandroff-compactifications of discrete spaces and D-compact.