Advances in Interdisciplinary Applied Discrete Mathematics

The following sections are included:

• Preface

• Contents

One of the fascinating features of mathematics is that the same ideas, concepts, techniques, models, and structures find applications in diverse disciplines. Or that results developed in one application find unexpected applications elsewhere. Within mathematics itself one finds a similar phenomenon: the same structure occurs with diferent guises in various mathematical problem areas.

Beginning in the mid 1970s, F.R. McMorris made significant contributions to character compatibility analysis by using his considerable mathematical talent to “prove” algorithms that I had previously conjectured, among them the so-called potential compatibility algorithm for qualitative taxonomic characters. Since then, this algorithm has become the basis for a wide variety of character compatibility analyses. Here I review the basic concepts of character compatibility analysis, describe McMorris' contributions to character compatibility analyses, review some of their applications, and present some ideas for future applications.

2 × 2 Tables are frequently encountered in various fields of science, including biometrics, psychology and ecology. To summarize the data in a 2 × 2 table it is convenient to calculate a statistic that quantifies in some way the degree of association or agreement between the rows and columns. The literature contains a vast amount of such relational statistics for 2 × 2 tables, many of which are just functions of the four cells a, b, c and d of the 2 × 2 table. In this paper we review the important ones. Furthermore, we show how many of the functions based on the four quantities a, b, c and d are related to one another by reviewing families of relational statistics from the literature. A statistic must be considered in the context of the data-analytic study of which it is a part. Studying families of statistics provides insight into how one statistic can be interpreted and is related to other statistics. The overview provides insights that may be helpful to researchers from various fields of science in deciding what statistic to use in applications or for studying theoretical properties.

Two applications of intersection graphs are presented—to protein interaction in cellular processes, and to Bonferroni-type inequalities in probability theory. Each application exploits appropriate spanning subgraphs of an intersection graph.

The general problem in location theory deals with functions that find sites on a graph (discrete case) or network (continuous case) in such a way as to minimize some cost (or maximize some benefit) to a given set of clients represented by vertices on the graph or points on the network. The axiomatic approach seeks to uniquely distinguish, by using a list of intuitively pleasing axioms, certain specific location functions among all the arbitrary functions that address this problem. In this chapter we survey results for three popular location functions (center, mean, median) in both the discrete and continuous cases. Some new results are presented for the median function on median networks.

Median graphs are a common generalization of trees and hypercubes in the following sense: for any three vertices u, u, w there exists a unique x lying on a ashortest path between any pair of u, u, w. The origins of median graphs have to be found within pure mathematics: they arose from semilattices, ternary algebras, and Helly hypergraphs. Form the view point of mathematics they form a very interesting class: a rich structure theory has been developed, and there is still much more to come. Another interesting feature is that median graphs appear in different guises in many other mathematical areas. But equally important is that median graphs and median-type structures have many applications in such diverse fields as: mathematical biology, psychology, chemistry, economics, literary history, location theory, voting theory, and the like. This chapter provides an introduction into the structure theory of median graphs. It surveys median structures within mathematics and presents a concise overview of the many applications.

In 1982, Slater defined and studied path subgraph analogues to the center, median, and branch weight centroid of a tree. We define three families of central substructures of trees, including three types of central subtrees of degree at most D, which yield the center, median, and centroid vertices for D = 0 and Slater's path analogues for D = 2. We generalize these results for several types of sub-structures in trees, each yielding three families of subtrees suggested by the three centrality measures involved with the center (eccentricity), the median (distance), and the branch weight centroid (branch weight). We present a theoretical framework in which several previous results sit. We prove that, in a tree, each type of generalized center and generalized centroid is unique and discuss algorithms for finding them. We also discuss the non-uniqueness of our generalized median and an algorithm to find one.

Consider an election where there are two alternatives and n ≥ 3 voters. For any integer q such that , the winner of the election with respect to absolute q-majority rule is the alternative that receives at least q votes. In this chapter, various generalizations of absolute q-majority rule are presented from an axiomatic point of view.

The classical measures of the “middle” of a tree include the center and the median. It is well known that another seemingly different measure, the branch weight centroid of a tree, yields the same middle as the median. Many other descriptions of “middleness” of a tree are not so well known, some of which also yield the same set of vertices as the median. In this survey we gather together many descriptions of middle sets in trees, some of which yield the same set of vertices as the median, and others that are distinct from the center and the median. We discuss, in turn, the center, the median, the branch weight centroid, the absolute p-center, the vertex p-center, the absolute p-median, the vertex p-center, the security center, the accretion center, the telephone center, the weight balance center, the latency center, the pairing center, the processing center, the leaf weight median, the leaf branch weight centroid, the n-th power center of gravity, the distance balance center, the k-nucleus, the k-branch weight centroid, the R-center, the k-centrum, the k-ball branch weight centroid, the k-ball l-path branch weight centroid, the k-processing center, the centdian (or cendian), the R-median, the R-branch weight centroid, the k-broadcast center, the distance balanced edge center, the weight balanced edge center, the Steiner k-center, the Steiner k-median, a central k-tree, the subtree center, the majorization center, the cutting center, the centrix, the security centroid, the harmonic center, the path center, a path median (core), and the path centroid (spine). We also mention some general central subtrees of maximum degree D that generalize some of the previous concepts, and we conclude with a further generalization involving hereditary class centrality. We also reference some work on tree networks.

When a port needs to be reopened after closure due to a natural disaster or terrorist event or domestic dispute, certain goods on incoming ships might be in short supply. This paper formulates the problem of scheduling the unloading of waiting ships to take into account the desired arrival times, quantities, and designated priorities of goods on those ships. Several objective functions are defined, special cases are discussed, and the relevant literature is surveyed.

Several results in consensus theory indicate that it is impossible to obtain conclusions should the rules satisfy certain seemingly innocuous but desired properties. As these conclusions create a barrier for progress, it is important to find ways to circumvent the dificulties. In this paper, a source of these complications is identified, and ways to combat the problem are indicated.

In this chapter we discuss the contributions of F.R. McMorris to discrete mathematics and its applications on the occasion of his retirement in 2008.

The following sections are included:

• Author Index

• Subject Index

• Symbol Index