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.

In this paper, we show that for every modular lattice \(L\), if its size is at least three times its excess, then each component of its direct product decomposition is isomorphic to one of the following: a Boolean lattice of rank one \(B_1\), a chain of length two \(3\), a diamond \(M_3\), and \(M_4\), where \(M_n\) is a modular lattice of rank two which has exactly \(n\) atoms.