The toughness \(t(G)\) of a noncomplete graph \(G\) is defined as

\[t(G) = \min \left\{ \frac{|S|}{\omega(G – S)} \mid S \subset V(G), \omega(G – S) \geq 2 \right\},\]

where \(\omega(G – S)\) is the number of components of \(G – S\). We also define \(t(K_n) = +\infty\) for every \(n\).

The total graph \(T(G)\) of a graph \(G\) is the graph whose vertex set can be put in one-to-one correspondence with the set \(V(G) \cup E(G)\) such that two vertices of \(T(G)\) are adjacent if and only if the corresponding elements of \(G\) are adjacent or incident.

In this article, we study the toughness of the total graph \(T(G)\) of a graph \(G\) on at least \(3\) vertices and give especially that \(t(T(G)) = t(G)\) if \(\kappa(G) = \lambda(G)\) and \(\kappa(G) \leq 2\), where \(\kappa(G)\) and \(\lambda(G)\) are the vertex and the edge-connectivity of \(G\), respectively.

We shall consider a problem of finding an ‘optimum’ tree which is closely related to the network flow problem proposed by Ford and Fulkerson, and call the solution to this problem a lexicographically optimum traffic tree (LOTT). Before examining this problem in detail, we shall review the problem of finding an optimum requirement spanning tree (ORST) studied by Hu, which is also related to the network flow problem. We can regard the LOTT problem as a min-max problem and the ORST problem as a min-sum problem. It shall be shown that, while LOTTs and ORSTs coincide completely without maximum degree constraints, they do not always coincide with the constraints. Further, we shall show that LOTTs can be expressed by simple recursion in a special case.

It is well known that some graph-theoretic extremal questions play a significant role in the investigation of communication network vulnerability. Answering questions concerning the realizability of graph invariants also solves several of these extremal problems. We define a \((p, q, \kappa, \Delta)\) graph as a graph having \(p\) points, \(q\) lines, point connectivity \(\kappa\) and maximum degree \(\Delta\). An arbitrary quadruple of integers \((a, b, c, d)\) is called \((p, q, \kappa, \Delta)\) realizable if there is a \((p, q, \kappa, \Delta)\) graph with \(p = a, q = b, \kappa = c\) and \(\Delta = d\). Necessary and sufficient conditions for a quadruple to be \((p, q, \kappa, \Delta)\) realizable are derived. In earlier papers, Boesch and Suffel gave necessary and sufficient conditions for \((p, q, \kappa)\), \((p, q, \lambda)\), \((p, q, \delta)\), \((p, \Delta, \delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability, where \(\lambda\) denotes the line connectivity of a graph and \(\delta\) denotes the minimum degree for all points in a graph.

We introduce the concept of a free \(a\)-valuation of a graph, and prove that the vertex-disjoint union of any collection of graphs with free \(\alpha\)-valuations has an \(\alpha\)-valuation. Many bipartite graphs have free \(\alpha\)-valuations, including the complete bipartite graph \(K_{m,n}\) when \(m > 1\) and \(n > 2\), and the \(d\)-cube \(Q_d\) for \(d > 2\).

Let \(G\) be a \(2\)-connected simple graph with order \(n\) (\(n \geq 5\)) and minimum degree \(5\). This paper proves that if for any two vertices \(u,v\) of \(G\) at distance two there holds \(|N(u) \bigcup N(v)| \geq n – \delta\), then \(G\) is vertex-pancyclic with a few exceptions.

Various \(n\)-color restricted partition functions are studied. Two different \(n\)-color analogues of the Gaussian polynomials are given.

There is a lexicographic ordering of \((0, 1)\)-tuples. Thus, the rows of a \((0, 1)\)-matrix can be ordered lexicographically decreasing from the top by permutations, or analogously the columns from the left. It is shown that \((0, 1)\)-matrices allow a simultaneous ordering of the rows and the columns. Those matrices are called doubly ordered, and their structure is determined. An answer is given to the question of whether a \((0, 1)\)-matrix can be transformed into a block diagonal matrix by permutations of the rows and the columns; in fact, the double ordering of a \((0, 1)\)-matrix already displays the finest block diagonal structure. Moreover, fast algorithms are presented that double order a \((0, 1)\)-matrix.

In this paper, we show that a graph \(G\) with \(e \geq 6\) edges contains at most \(\frac{h(h-1)(h-2)(h-3)}{2}\) paths of length three, where \(h \geq 0\) satisfies \(\frac{h(h-1)}{2} = e\). It follows immediately that \(G\) contains at most \(\frac{h(h-1)(h-2)(h-3)}{8}\) cycles of length four. For \(e > 6\), the bounds will be attained if and only if \(h\) is an integer and \(G\) is the union of \(K_h\) and isolated vertices. The bounds improve those found recently by Bollobás and Sarkar.

Let \(p > 2\) be a prime, and \(G = C_{p^{e_1}} \oplus \ldots \oplus C_{p^{e_k}}\) (\(1 \leq e_1 \leq \cdots \leq e_k\)) a finite abelian \(p\)-group. We prove that \(1 + 2\sum_{i=1}^{k}(p^{e_i} – 1)\) is the smallest integer \(t\) such that every sequence of \(t\) elements in \(G\) contains a zero-sum subsequence of odd length. As a consequence, we derive that if \(p^{e_k} \geq 1 + \sum_{i=1}^{k-1} (p^{e_i} – 1)\), then every sequence of \(4p^{e_k} – 3 + 2\sum_{i=1}{k-1} (p^{e_i} – 1)\) elements in \(G\) contains a zero-sum subsequence of length \(p^{e_k}\).

Solutions for the edge-isoperimetric problem on the graphs of the triangular and hexagonal tessellations of the Euclidean plane are given. The proofs are based on the fact that their symmetry group is Coxeter. In each case, there is a certain nice quotient of the stability order of the graph (which is itself a quotient of the Bruhat order of the Coxeter group by a parabolic subgroup).