Denote the total domination number of a graph \(G\) by \(\gamma_t(G)\). A graph \(G\) is said to be total domination edge critical, or simply \(\gamma_t\)-critical, if \(\gamma_t(G+e) < \gamma_t(G)\) for each edge \(e \in E(\overline{G})\). For \(\gamma_t\)-critical graphs \(G\), that is, \(\gamma_t\)-critical graphs with \(\gamma_t(G) = 3\), the diameter of \(G\) is either \(2\) or \(3\). We study the \(3_t\)-critical graphs \(G\) with \(diam(G) = 2\).

We tackle the problem of estimating the Shannon capacity of cycles of odd length. We present some strategies which allow us to find tight bounds on the Shannon capacity of cycles of various odd lengths, and suggest that the difficulty of obtaining a general result may be related to different behaviours of the capacity, depending on the “structure” of the odd integer representing the cycle length. We also describe the outcomes of some experiments, from which we derive the evidence that the Shannon capacity of odd cycles is extremely close to the value of the Lovasz theta function.

In a recent paper [1] Maynard answered a question of Harary and Manvel [2] about the reconstruction of \(square-celled \;animals\). One of his results relied on a general algebraic approach due to Alon, Caro, Krasikov, and Roditty [3]. Applying arguments of a more combinatorial nature we improve this result and give an answer to a question raised by him in [1].

Recently, in connection with the classification problem for non-Cayley tetravalent metacirculant graphs, three families of special tetravalent metacirculant graphs, denoted by \(\Phi_1, \Phi_2\), and \(\Phi_3\), have been defined [11]. It has also been shown [11] that any non-Cayley tetravalent metacirculant graph is isomorphic to a union of disjoint copies of a graph in one of the families \(\Phi_1, \Phi_2\), or \(\Phi_3\). A natural question raised from the result is whether all graphs in these families are non-Cayley. In this paper we determine the automorphism groups of all graphs in the family \(\Phi_2\). As a corollary, we show that every graph in \(\Phi_2\) is a connected non-Cayley tetravalent metacirculant graph.

Let \(G\) be a connected graph and \(S \subset E(G)\). If \(G – S\) is disconnected without isolated vertices, then \(S\) is called a restricted edge-cut of \(G\). The restricted edge-connectivity \(\lambda’ = \lambda'(G)\) of \(G\) is the minimum cardinality over all restricted edge-cuts of \(G\). A connected graph \(G\) is called \(\lambda’\)-connected, if \(\lambda'(G)\) exists. For a \(\lambda’\)-connected graph \(G\), Esfahanian and Hakimi have shown, in 1988, that \(\lambda'(G) \leq \xi(G)\), where \(\xi(G)\) is the minimum edge-degree. A \(\lambda’\)-connected graph \(G\) is called \(\lambda’\)-optimal, if \(\lambda'(G) = \xi(G)\).

Let \(G_1\) and \(G_2\) be two disjoint \(\lambda’\)-optimal graphs. In this paper we investigate the cartesian product \(G_1 \times G_2\) to be \(\lambda’\)-optimal. In addition, we discuss the same question for another operation on \(G_1\) and \(G_2\), and we generalize a recent theorem of J.-M. Xu on non \(\lambda’\)-optimal graphs.

The niche graph of a digraph \(D\) is the undirected graph defined on the same vertex set in which two vertices are adjacent if they share either a common in-neighbor or a common out-neighbor in \(D\). A hierarchy of graphs exists, depending on the condition of being the niche graph of a digraph having, respectively, no cycles, no cycles of length two, no loops, or loops. Our goal is to classify in this hierarchy all graphs of order \(n \geq 3\) having a generated subgraph isomorphic to the discrete graph on \(n – 2\) vertices.

We enumerate the bases of the bicircular matroid on \(K_{m,n}\). The structure of bases of the bicircular matroid in relation to the bases of the cycle matroid is explored. The techniques herein may enable the enumeration of the bases of bicircular matroids on larger classes of graphs; indeed one of the motivations for this work is to show the extendibility of the techniques recently used to enumerate the bases of the bicircular matroid on \(K_n\).

Motivated by the work of Granville, Moisiadis and Rees, we consider in this paper complementary \(P_3\)-packings of \(K_v\). We prove that a maximum complementary \(P_3\)-packing of \(K_v\) (with \(\lfloor\frac{v}{4} \lfloor \frac{2(v-1)}{3}\rfloor \rfloor P_3s\)) exists for all integers \(v \geq 4\), except for \(v = 9\) and possibly for \(v \in \{24, 27, 30, 33, 36, 39, 42, 57\}\).

It is proved that there is no maximal partial spread of size \(115\) in \(\mathrm{PG}(3,11)\).

In this short note, using the method developed in [10] and [11], we construct a highly symmetrical, non-simple, attractive \(7\)-Venn diagram. This diagram has the minimum number of vertices, \(21\). The only similar two, published in [1] and [11], differ from ours in many ways. One of them was found by computer search [1]. Both of them are “necklace” type Venn diagrams (see [14] for definition), but ours is not.

A graph is a unit interval graph (respectively, an \(\tilde{n}\)-graph) if we can assign to each vertex an open interval of unit length (respectively, a set of \(n\) consecutive integers) so that edges correspond to pairs of intervals (respectively, of sets) that overlap. Sakai [14] and Troxell [18] provide a linear time algorithm to find the smallest integer \(n\) so that a unit interval graph is an \(\mathbb{A}\)-graph, for the particular case of reduced connected graphs with chromatic number \(3\). This work shows how to obtain such smallest \(n\) for arbitrary graphs, by establishing a relationship with the work by Bogart and Stellpflug [1] in the theory of semiorders.

For words of length \(n\), generated by independent geometric random variables, we consider the probability that these words avoid a given consecutive \(3\)-letter pattern. As a consequence, we count permutations in \(S_n\) avoiding consecutive \(3\)-letter patterns.

A mimeomatroid is a matroid union of a matroid with itself. We develop several properties of mimeomatroids, including a generalization of Rado’s theorem, and prove a weakened version of a matroid conjecture by Rota [2].

The well-known Marriage Lemma states that a bipartite regular graph has a perfect matching. We define a bipartite graph \(G\) with bipartition \((X,Y)\) to be semi-regular if both \(x \mapsto\) deg \(x,x \in X\) and \(y \mapsto\) deg \(y, y \in Y\) are constant. The purpose of this note is to show that if \(G\) is bipartite and semi-regular, and if \(|X| < |Y|\), then there is a matching which saturates \(|X|\). (Actually, we prove this for a condition weaker than semi-regular.) As an application, we show that various subgraphs of a hypercube have saturating matchings. We also exhibit classes of bipartite graphs, some of them semi-regular, whose vertices are the vertices of various weights in the hypercube \(Q_n\), but which are not subgraphs of \(Q_n\).

The sum graph of a set \(S\) of positive integers is the graph \(G^+(S)\) having \(S\) as its vertex set, with two vertices adjacent if and only if their sum is in \(S\). A graph \(G\) is called a sum graph if it is isomorphic to the sum graph \(G^+(S)\) of some finite subset \(S\) of \(N\). An integral sum graph is defined just as the sum graph, the difference being that \(S\) is a subset of \(Z\) instead of \(N\). The sum number of a graph \(G\) is defined as the smallest number of isolated vertices when added to \(G\) results in a sum graph. The integral sum number of \(G\) is defined analogously. In this paper, we study some classes of integral sum graphs.

We say that a graph \(F\) strongly arrows \((G,H)\) and write \(F \longmapsto (G,H)\) if for every edge-coloring of \(F\) with colors red and blue, a red \(G\) or a blue \(H\) occurs as an induced subgraph of \(F\). Induced Ramsey numbers are defined by \(r^*(G,H) = \min\{|V(F)| : F \longmapsto (G,H)\}\).
The value of \(r^*(G,H)\) is finite for all graphs, and good upper bounds on induced Ramsey numbers in general, and for particular families of graphs are known. Most of these results, however, use the probabilistic method, and therefore do not yield explicit constructions. This paper provides several constructions for upper bounds on \(r^*(G,H)\), including:\(r^*(C_n) = r^*(C_n,C_n) \leq c^{(logn)^2}\), \(r^*(T,K_n) \leq |T|n^{|T|log|T|}\), \(r^*(B,C_n) \leq |B|^{\lceil log n \rceil +4}\) ,where \(T\) is a tree, \(B\) is bipartite, \(K_n\) is the complete graph on \(n\) vertices, and \(C_n\) is a cycle on \(n\) vertices. We also have some new upper bounds for small graphs: \(r^*(K_3 + e) \leq 21\), and \(r^*(K_4 – e) \leq 46\).

An \(L(2,1)\)-labeling of a graph \(G\) is a function \(f\) from the vertex set \(V(G)\) to the set of all nonnegative integers such that \(|f(x)-f(y)|\geq 2\quad\text{if}\quad d_G(x,y)=1\) and \(|f(x)-f(y)|\geq 1\quad\text{if}\quad d_G(x,y)=2\). The \(L(2,1)\)-labeling problem is to find the smallest number \(\lambda(G)\) such that there exists an \(L(2,1)\)-labeling function with no label greater than \(\lambda(G)\). Motivated by the channel assignment problem introduced by Hale, the \(L(2,1)\)-labeling problem has been extensively studied in the past decade. In this paper, we study this concept for digraphs. In particular, results on ditrees are given.

Let \(G\) be a simple graph with vertex set \(V\) and edge set \(E\). A vertex labeling \(\overline{f}: V \to \{0,1\}\) induces an edge labeling \(\overline{f}: E \to \{0,1\}\) defined by \(f(uv) = |f(u) – f(v)|\) .Let \(v_f(0),v_f(1)\) denote the number of vertices \(v\) with \(f(v) = 0\) and \(f(v) = 1\) respectively. Let \(e_f(0),e_f(1)\) be similarly defined. A graph is said to be cordial if there exists a vertex labeling \(f\) such that \(|v_f(0) – vf(1)| \leq 1\) and \(|e_f(0) – e_f(1)| \leq 1\).

A \(t\)-uniform homeomorph \(P_t(G)\) of \(G\) is the graph obtained by replacing all edges of \(G\) by vertex disjoint paths of length \(t\). In this paper we investigate the cordiality of \(P_t(G)\), when \(G\) itself is cordial. We find, wherever possible, a cordial labeling of \(P_t(G)\), whose restriction to \(G\) is the original cordial labeling of \(G\) and prove that for a cordial graph \(G\) and a positive integer \(t\), (1) \(P_t(G)\) is cordial whenever \(t\) is odd, (2) for \(t \equiv 2 \pmod{4}\) a cordial labeling \(g\) of \(G\) can be extended to a cordial labeling \(f\) of \(P_t(G)\) iff \(e_0\) is even, (3) for \(t \equiv 0 \pmod{4}\), a cordial labeling \(g\) of \(G\) can be extended to a cordial labeling \(f\) of \(P_t(G)\) iff \(e_1\) is even.

The domination graph \(dom(D)\) of a digraph \(D\) has the same vertex set as \(D\), and \(\{u,v\}\) is an edge if and only if for every \(w\), either \((u,w)\) or \((v,w)\) is an arc of \(D\). In earlier work we have shown that if \(G\) is a domination graph of a tournament, then \(G\) is either a forest of caterpillars or an odd cycle with additional pendant vertices or isolated vertices. We have also earlier characterized those connected graphs and forests of non-trivial caterpillars that are domination graphs of tournaments. We complete the characterization of domination graphs of tournaments by describing domination graphs with isolated vertices.

It is proved that the \(n\)-cone \(C_m \vee K_n^c\) is graceful for any \(n \geq 1\) and \(m = 0\) or \(3 \pmod{12}\). The gracefulness of the following \(n\)-cones is also established: \(C_4 \vee K_n^c\), \(C_5 \vee K_2^c\), \(C_7 \vee K_n^c\), \(C_9 \vee K_2^c\), \(C_{11} \vee K_n^c\), \(C_{19} \vee K_n^c\). This partially answers the question of gracefulness of \(n\)-cones which is listed as an open problem in the survey article by J.A. Gallian.

We tackle the problem of estimating the Shannon capacity of cycles of odd length. We present some strategies which allow us to find tight bounds on the Shannon capacity of cycles of various odd lengths, and suggest that the difficulty of obtaining a general result may be related to different behaviours of the capacity, depending on the “structure” of the odd integer representing the cycle length. We also describe the outcomes of some experiments, from which we derive the evidence that the Shannon capacity of odd cycles is extremely close to the value of the Lovasz theta function.

Upper and lower bounds are given for the toughness of generalized Petersen graphs. A lower bound of \(1\) is established for \(t(G(n,k))\) for all \(n\) and \(k\). This bound of \(1\) is shown to be sharp if \(n = 2k\) or if \(n\) is even and \(k\) is odd. The upper bounds depend on the parity of \(k\). For \(k\) odd, the upper bound \(\frac{n}{n-\frac{n+1}{2}}\) is established. For \(k\) even, the value \(\frac{2k}{2k-1}\) is shown to be an asymptotic upper bound. Computer verification shows the reasonableness of these bounds for small values of \(n\) and \(k\).

Suppose \(G\) is a graph. The minimum number of paths (trees, forests, linear forests, star forests, complete bipartite graphs, respectively) needed to decompose the edges of \(G\) is called the path number (tree number, arboricity, linear arboricity, star arboricity and biclique number, respectively) of \(G\). These numbers are denoted by \(p(G), t(G), a(G), la(G), sa(G), r(G)\), respectively. For integers \(1 \leq k \leq n\), let \(C_{n,k}\) be the graph with vertex set \(\{a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n\}\) and edge set \(\{a_ib_j :i=1,2,\ldots ,n,j \equiv i+1,i+2, \ldots ,i+k \text{(mod n)}\}\). We call \(C_{n,k}\) a crown. In this paper, we prove the following results:

1. \(p(C_{n,k}) = \begin{cases}
   n & \text{if \(k\) is odd}, \\
   {(\frac{k}{2})+1} & \text{if \(k\) is even}.
   \end{cases}\)
2. \(a(C_{n,k}) = t(C_{n,k}) = la(C_{n,k}) = \left\lceil \frac{k+1}{2} \right\rceil\) if \(k \geq 2\).
3. For \(k \geq 3\) and \(k \in \{3,5\} \cup \{n-3,n-2,n-1\}\),
   \[sa(C_{n,k}) = \begin{cases}
   \left\lceil \frac{k}{2} \right\rceil + 1 & \text{if \(k\) is odd}, \\
   \left\lceil \frac{k}{2} \right\rceil + 2 & \text{if \(k\) is even}.
   \end{cases}\]
4. \(r(C_{n,k}) = n\) if \(k \leq \frac{n+1}{2}\) or \(\gcd(k,n) = 1\).

Due to (3), (4), we propose the following conjectures.

\(\textbf{Conjecture A}\). For \(3 \leq k \leq n-1\),
\[sa(C_{n,k}) = \begin{cases}
\left\lceil \frac{k}{2} \right\rceil + 1 & \text{if \(k\) is odd}, \\
\left\lceil \frac{k}{2} \right\rceil + 2 & \text{if \(k\) is even}.
\end{cases}\]
\(\textbf{Conjecture B}\). For \(1 \leq k \leq n-1\), \(r(C_{n,k}) = n\).