Narrow Results

In this paper, we introduce a new variant of domination called the outer-paired domination. For a graph $G=(V,E)$, an outer-paired dominating set $D\subseteq V$ is a dominating set of $G$ such that the induced subgraph of $V\setminus D$ contains a perfect matching. The outer-paired domination number of a graph $G$ is the cardinality of a minimum outer-paired dominating set of $G$. We show that finding the outer-paired domination number of a graph $G$ is NP-hard on bipartite graphs, chordal graphs, and planar graphs. We also propose a linear-time algorithm for solving the outer-paired domination problem on trees.

In 1956, Nordhaus and Gaddum gave lower and upper bounds on the sum and the product of the chromatic number of a graph and its complement, in terms of the order of the graph. Since then, any bound on the sum and/or the product of an invariant in a graph $G$ and the same invariant in the complement $G^c$ of $G$ is called a Nordhaus-Gaddum type inequality or relation. The Nordhaus-Gaddum type inequalities for connectivity have been studied by several authors. For a bipartite graph $G=G[X,Y]$ with bipartition ($X,Y$), its bipartite complementary graph $G^{bc}$ is a bipartite graph with $V(G^{bc})=V(G)$ and $E(G^{bc})=\{xy:x\in X,y\in Y$ and $xy\notin E(G)\}$. In this paper, we obtain the Nordhaus-Gaddum type inequalities for connectivity of bipartite graphs and its bipartite complementary graphs. Furthermore, we prove that these inequalities are best possible.

Community search over bipartite graphs has attracted significant interest recently. In many applications such as the user–item bipartite graph in e-commerce and customer–movie bipartite graph in movie rating website, nodes tend to have attributes. However, the previous community search algorithms on bipartite graphs ignore attributes, thus making them to return results with poor cohesion with respect to their node attributes. In this paper, we study the community search problem on attributed bipartite graphs. Given a query vertex $q$, we aim to find the attributed $(\alpha ,\beta )$-communities of $G$, where the structure cohesiveness of the community is described by the $(\alpha ,\beta )$-core model, and the attribute similarity of two groups of nodes in the subgraph is maximized. In order to retrieve attributed communities from bipartite graphs, we first propose a basic algorithm composed of two steps: the generation and verification of candidate keyword sets, and then two improved query algorithms Inc and Dec are proposed. Inc is proposed considering the anti-monotonicity property of attributed bipartite graphs, then we adopt different generating methods and verify the order of candidate keyword sets and propose the Dec algorithm. After evaluating our solutions on eight large graphs, the experimental results demonstrate that our methods are effective and efficient in querying the attributed communities on bipartite graphs.

We introduce a recovery algorithm for low-density parity-check codes that provides substantial coding gain over the conventional method. Concisely, it consists of an inference procedure based on successive decoding rounds using different subsets of bit nodes from the bipartite graph representing the code. The technique also sheds light on certain characteristics of the sum–product algorithm and effectively copes with the problems of trapping sets, cycles, and other anomalies that adversely affect the performance LDPC codes.

We investigate several generalizations of the Hopf algebra MQSym whose constructions come from labelings of special diagrams in bijection with packed matrices. Their products come either from the Hopf algebras WSym or WQSym, respectively built on integer set partitions and set compositions. Realizations on bi-word are exhibited, and it is shown how these algebras fit into a commutative diagram. Hopf deformations and dendriform structures are also considered for some algebras in the picture.

We prove that every embedding of K_2n+1,2n+1 into ℝ³ contains a non-split link of n components. Further, given an embedding of K_2n+1,2n+1 in ℝ³, every edge of K_2n+1,2n+1 is contained in a non-split n-component link in K_2n+1,2n+1.

Suppose that G = (V₀ ∪ V₁, E) is a bipartite graph with two partite sets V₀ and V₁ of equal size. Let x and y be two arbitrary distinct, vertices and let w be another vertex different from x and y. G is said to be 1-vertex-Hamiltonian-laceable if G - w satisfies the following three properties:

P1. There is a (|V₀| + |V₁| - 2)-length path between x and y, where x and y are in the same partite set and w is in the other partite set;

P2. There is a (|V₀| + |V₁| - 3)-length path between x and y, where x and y are in different partite sets and w is in any partite set;

P3. There is a (|V₀| + |V₁| - 4)-length path between x and y, where x, y, w are in the same partite set.

Let F_e be the set of faulty edges of an n-dimensional hypercube Q_n. In this paper, we show that Q_n - F_e (the graph obtained by deleting all edges of F_e from Q_n) remains 1-vertex-Hamiltonian-laceable when |F_e| ≤ n - 3.

In this paper, we compute the graded Betti numbers of toric algebras of certain bipartite graphs $G_{r,s,d}$. Also, the Castelnuovo–Mumford regularity, Hilbert series and multiplicity of $K[G_{r,s,d}]$ are explicitly determined.

The aim of this paper is to show that any finite undirected bipartite graph can be considered as a polynomial $P\in \mathbb{N}[x]$, and any directed finite bipartite graph can be considered as a polynomial $P\in \mathbb{N}[x,y]$, and vise verse. We also show that the multiplication in the semirings $\mathbb{N}[x]$, $\mathbb{N}[x,y]$ corresponds to an operation of the corresponding graphs. This operation is exactly the product of Petri nets in the sense of Winskel [G. Winskel and M. Nielsen, Models of concurrency, in Handbook of Logic in Computer Science, Vol. 4, eds. Abamsky, Gabbay and Maibaum (Oxford University Press, 1995), pp. 1–148]. As an application, we give an approach to dividing in the semirings $\mathbb{N}[x]$, $\mathbb{N}[x,y]$, and a criteria for parallalization of Petri nets. Finally, we endow the set of all bipartite graphs with the Zariski topology.

Let $R=k[x_1,\dots ,x_n]$ be the polynomial ring over a field $k$, $G$ be a graph on vertex set $V=\{x_1,\dots ,x_n\}$ and $I=I(G)$ be its edge ideal. In this paper, we study bi-sequentially Cohen–Macaulay (bi-SCM) bipartite graphs and as consequence we classify all bi-SCM tree graphs. Furthermore, if $R/I$ is bi-SCM then we determine the projective dimension of $R/I$. Moreover, we give some examples.

Let $I$ be an ideal of the form

In this paper, we first give some sufficient criteria for normality of monomial ideals. As applications, we show that closed neighborhood ideals of complete bipartite graphs are normal, and hence satisfy the (strong) persistence property. We also prove that dominating ideals of complete bipartite graphs are nearly normally torsion-free. In addition, we show that dominating ideals of $h$-wheel graphs, under certain condition, are normal.

In this paper, Betti numbers are evaluated for several classes of graphs whose complements are bipartite graphs. Relations are established for the general case, and counting formulae are given in several particular cases, including the union of several mutually disjoint complete graphs.

Let $I(G)$ be a topological index of a graph. If $I(G+e)<I(G)$ (or $I(G+e)>I(G)$, respectively) for each edge $e\notin G$, then $I(G)$ is monotonically decreasing (or increasing, respectively) with the addition of edges. In this paper, by a unified approach, we determine the extremal values of some monotonic topological indices, including the Wiener index, the hyper-Wiener index, the Harary index, the connective eccentricity index, the eccentricity distance sum, among all connected bipartite graphs with a given number of cut edges, and characterize the corresponding extremal graphs, respectively.

Graph protection using mobile guards has received a lot of attention in the literature. It has been considered in different forms, including Eternal Dominating set, Eternal Independent set and Eternal Vertex Cover set. In this paper, we introduce and study two new models of graph protection, namely Eternal Feedback Vertex Sets (EFVS) and m-Eternal Feedback Vertex Sets (m-EFVS). Both models are based on an initial selection of a feedback vertex set (FVS), where a vertex in FVS can be replaced with a neighboring vertex such that the resulting set is a FVS too. We prove bounds for both the eternal and m-eternal feedback vertex numbers on, mainly, distance graphs, circulant graphs and grids. Also, we deduce other inequalities for both parameters on cycles, complete graphs and complete bipartite graphs.