Narrow Results

The aim of this work is to compare symbolic and ordinary powers of monomial ideals using commutative algebra and combinatorics. Monomial ideals whose symbolic and ordinary powers coincide are called Simis ideals. Weighted monomial ideals are defined by assigning linear weights to monomials. We examine Simis and normally torsion-free ideals, relate some of the properties of monomial ideals and weighted monomial ideals, and present a structure theorem for edge ideals of $d$-uniform clutters whose ideal of covers is Simis in degree $d$. One of our main results is a combinatorial classification of when the dual of the edge ideal of a weighted oriented graph is Simis in degree $2$.

An innovative approach for automated plant disease identification has been proposed in this study. The main contribution of this study is the introduction of a bipartite graph-based clustering technique that has been used for image segmentation, a feature extraction methodology using Self-Organizing Map (SOM), and a ray tracing method. Numerous research works have already been done in this area with their respective merits and demerits. But this bipartite graph-based clustering for image segmentation and feature extraction using SOM and ray tracing techniques has not been used in any of these studies as far as we are aware. The core idea behind this clustering technique is to represent similar spatial data points using a bipartite graph and then singular value decomposition has been used on that graph for clustering. It is common to use SOM for clustering. However, in this study, SOM has been used for feature extraction. First, a spatial dependency matrix based on the pixel value of the gray image has been constructed using SOM. Then some statistical features have been computed from this matrix. Using the ray tracing method, the length of the most extended cluster, i.e. the length of the most extended disease-affected patch, and the distribution of the clusters in the image have been computed. The accuracy of our model has been greatly enhanced using these features only. It has been experimented on disease-affected grape leaf images taken from the Plant Village Dataset. This model outperforms state-of-the-art models, which is shown in the experimental findingsresults section. Not only that, the proposed features produce better accuracy rather than using some existing features. This comparison has also been shown in the experimental findings. The result has been validated using K-fold cross-validation. Last, but not the least, these features produce good accuracy using different classifiers also.

A new kind of bipartite graph is defined in this paper. The work is motivated mainly from a graph introduced by Al-Kaseasbeh and Erfanian [A bipartite graph associated to elements and cosets of subgroups of a finite group, AIMS Math. 6(10) (2021) 10395–10404] and partially from the undirected power graph of a group and from the inclusion graph. For a nontrivial group $G$, we define a simple undirected bipartite graph $\mathrm{\Gamma }(G)$ with the vertex set $V(\mathrm{\Gamma }(G))=A\cup B$, where $A$ is the set of all elements of the group $G$ and $B$ is the set of all subgroups $H$ of $G$ such that $H\ne \{e\}$ and two vertices $a\in A$ and $H\in B$ are adjacent if and only if $a^2\in H$. Here, we classify all the finite groups $G$ whose bipartite graphs $\mathrm{\Gamma }(G)$ are planar. In addition, we also classify the finite groups $G$ such that $\mathrm{\Gamma }(G)$ is outerplanar, maximal planar, maximal outerplanar, star, tree, claw graph, respectively. The planarity of the graph $\mathrm{\Gamma }(G)$ corresponding to an infinite group $G$ has also been investigated here. It is also observed that $\mathrm{\Gamma }(G)$ satisfies Vizing’s conjecture.

Let G be a connected bipartite graph with with bipartition (X, Y) such that |X| ≥ |Y| (≥ 2). Put n = |X|, m = |Y| and l = m + n. Suppose that, for all vertices x ∈ X and y ∈ Y, dist(x,y) = 3 implies d(x) + d(y) ≥ n + 1. We show that G contains a cycle of length 2m. We also give an efficient algorithm to obtain such a cycle. The complexity of this algorithm is O(l³). In case m = n, we find a hamiltonian cycle of G. This generalizes a result given in [10].

Let G be a connected graph. A set of vertices $\text{S }\subseteq \text{ V (G)}$ is called subverted from G if each of the vertices in S and the neighbor of S in G are deleted from G. By G/S we denote the survival subgraph that remains after S is subverted from G. A vertex set S is called a cut-strategy of G if G/S is disconnected, a clique, or ø. The vertex-neighbor-scattering number of G is defined by $\text{VNS(G) = }\underset{\text{S}\subseteq \text{V(G)}}{\text{max}}\text{{}\omega \text{(G/S)}\text{-}\mathrm{|S|}\text{}}$, where S is any cut-strategy of G, and ø(G/S) is the number of components of G/S. It is known that this parameter can be used to measure the vulnerability of spy networks and the computing problem of the parameter is NP-complete. In this paper, we discuss the vertex-neighbor-scattering number of bipartite graphs. The NP-completeness of the computing problem of this parameter is proven, and some upper and lower bounds of the parameter are also given.

Let G be a simple bipartite graph with bipartition (X, Y) such that |X|≥|Y|≥2. Put n=|X|, m=|Y| and p=m+n. Suppose, for each pair of nonadjacent vertices x∈X and y∈Y we have d(x)+d(y)≥n+1. We give an efficient algorithm to obtain a cycle of length 2m in G. The complexity of this algorithm is O(p²). In particular, if m=n, we have a hamiltonian cycle of G.

We describe here a technique of decomposition of bipartite graphs which seems to be as interesting within this context as the well known modular and split techniques for the decomposition of general graphs. In particular, we characterize by forbidden subgraphs the family of bipartite graphs which are totally decomposable (i.e. reducible to single vertices) with respect to our decomposition. This family contains previously known families of graphs such as bicographs and P₆-free bipartite graphs. As an application we provide polynomial solutions of optimization problems, some of them being NP-complete for general bipartite graphs.

In an online problem, the input is revealed one piece at a time. In every time step, the online algorithm has to produce a part of the output, based on the partial knowledge of the input. Such decisions are irrevocable, and thus online algorithms usually lead to nonoptimal solutions. The impact of the partial knowledge depends strongly on the problem. If the algorithm is allowed to read binary information about the future, the amount of bits read that allow the algorithm to solve the problem optimally is the so-called advice complexity. The quality of an online algorithm is measured by its competitive ratio, which compares its performance to that of an optimal offline algorithm.

In this paper we study online bipartite matchings focusing on the particular case of bipartite matchings in regular graphs. We give tight upper and lower bounds on the competitive ratio of the online deterministic bipartite matching problem. The competitive ratio turns out to be asymptotically equal to the known randomized competitive ratio. Afterwards, we present an upper and lower bound for the advice complexity of the online deterministic bipartite matching problem.

We have recently shown that one can obtain the numbers and sizes of modules of a software system from the eigenvectors of its modularity matrix symmetrized and weighted by an affinity matrix. However such a weighting still demands a suitable definition of an affinity. This paper offers an alternative way to obtain the same results by means of the eigenvectors of a Laplacian matrix, directly obtained from the modularity matrix without the need of weighting. These two formalizations stand in a mutual isomorphism. We call it bipartite isomorphism since it is most straightforwardly shown by deriving the Laplacian from the modularity matrix and vice versa through the intermediate bipartite graph between two separate sets: the structors’ and the functionals’ sets. This isomorphism is also demonstrated through the equation defining the Laplacian in terms of the modularity matrix, or by the direct mapping of the respective matrices’ eigenvectors. Both matrices and the bipartite graph reflect one central idea: modules are connected components with high cohesion. The Laplacian matrix technique, of which the Fiedler vector is of central importance, is illustrated by case studies. An important claim of this paper is that, independently of the modularity matrix- and Laplacian matrix-specific properties, behind these two alternative matrices there is just one unified algebraic theory of software composition — the Linear Software Models — here concerning the application of the matrices’ eigenvectors to software modularity.

The power graph of a group G is a simple graph whose vertex-set is G and two vertices x and y in G are adjacent if and only if one of them is a power of the other. The subgraph of is obtained by deleting the vertex 1 (the identity element of G). In this paper, we first investigate some properties of the power graph and its subgraph . We next provide necessary and sufficient conditions for a power graph to be a strongly regular graph, a bipartite graph or a planar graph. Finally, we obtain some infinite families of finite groups G for which the power graph contains some cut-edges.

Let $R$ be a commutative ring with identity, and let $Z(R)$ be the set of zero-divisors of $R$. The annihilator graph of $R$ is defined as the graph AG$(R)$ with the vertex set $Z{(R)}^{\ast }=Z(R)\backslash \{0\}$, and two distinct vertices $x$ and $y$ are adjacent if and only if ann${}_R(xy)\ne {\mathrm{\text{ann}}}_R(x)\cup {\mathrm{\text{ann}}}_R(y)$. In this paper, we study annihilator graphs of rings with equal clique number and chromatic number. For some classes of rings, we give an explicit formula for the clique number of annihilator graphs. Among other results, bipartite annihilator graphs of rings are characterized. Furthermore, some results on annihilator graphs with finite clique number are given.

We characterize all connected graphs with exactly three distinct normalized Laplacian eigenvalues among which one is equal to 1, and determine all connected bipartite graphs with at least one vertex of degree 1 having exactly four distinct normalized Laplacian eigenvalues. In addition, we find all unicyclic graphs with three or four distinct normalized Laplacian eigenvalues.

Let $X$ be a finite simple graph. The $2$-distance graph $D_2(X)$ of $X$ is the graph with the same vertex set as $X$ and two vertices are adjacent if and only if their distance in $X$ is exactly $2$. A graph $G$ is a $2$-distance graph if there exists a graph $X$ such that $D_2(X)\cong G$. In this paper, we give three characterizations of $2$-distance graphs, and find all graphs $X$ such that $D_2(X)\cong k{P}_2$ or $K_m\cup K_n$, where $k\ge 2$ is an integer, $P_2$ is the path of order $2$, and $K_m$ is the complete graph of order $m\ge 1$.

The tensor product and the Cartesian product of two graphs are very well-known graph products and studied in detail. Many graph parameters, particularly independence number, have been studied for these graph products. These two graph products have been generalized by $2$-tensor product and $2$-Cartesian product, respectively, and studied in detail. In this paper, we discuss the independence number for $2$-tensor product $G{\otimes }_{2}H$ and $2$-Cartesian product $G{\times }_{2}H$. In general, we obtain lower bound and upper bound for the independence number.

For a graph, the first (multiplicative) Zagreb index is equal to the sum (product) of squares of the vertex degrees, and the second (multiplicative) Zagreb index is equal to the sum (product) of products of the degrees of a pair of adjacent vertices. In this work, by a unified approach, we determine the extremal values of these Zagreb indices in terms of the (edge) connectivity and characterize the corresponding extremal graphs among all connected bipartite graphs of order $n$. Our results show that the extremal graphs of given (edge) connectivity regarding the Zagreb indices and multiplicative Zagreb indices do not completely coincide with other topological indices.

For $a,b\in ℝ$, the general eccentric distance sum of a connected graph $G$ is defined as ${\mathrm{\text{EDS}}}_{a,b}(G)={\sum }_{u\in V(G)}{[{\mathrm{\text{ecc}}}_G(u)]}^a{[D_G(u)]}^b$, where $V(G)$ is the vertex set of $G$, ${\mathrm{\text{ecc}}}_G(u)$ is the eccentricity of $u\in V(G)$, $D_G(u)={\sum }_{v\in V(G)}{d}_G(u,v)$ and $d_G(u,v)$ is the distance between vertices $u$ and $v$ in $G$. For $a\ge 0$ and $b\ge 1$, we present the graphs having the smallest general eccentric distance sum among graphs with given order and diameter, and among bipartite graphs with given order and odd diameter. The extremal graphs for the classical eccentric distance sum are corollaries of our results on the general eccentric distance sum.

Let $G$ be a finite group and ${\mathrm{\text{A}}}_G$ be the automorphism group of $G$ (i.e. $\mathrm{\text{Aut}}(G)$). We associated a bipartite graph, denoted by ${\mathrm{\Gamma }}_G$, to $G$ and its automorphism group $\mathrm{\text{Aut}}(G)$ as follows: two parts of the vertex set are $G\backslash L(G,Z(G))$ and ${\mathrm{\text{A}}}_G\backslash {\mathrm{\text{Aut}}}_c(G)$, where $L(G,Z(G))$ is the set of elements $g\in G$ such that $g^{-1}\alpha (g)\in Z(G)$ for all $\alpha \in {\mathrm{\text{A}}}_G$ and ${\mathrm{\text{Aut}}}_c(G)$ is the set of automorphisms $\beta \in {\mathrm{\text{A}}}_G$ such that $g^{-1}\beta (g)\in Z(G)$ for all $g\in G$. Two vertices $g\in G\backslash L(G,Z(G))$ and $\alpha \in {\mathrm{\text{A}}}_G\backslash {\mathrm{\text{Aut}}}_c(G)$ are adjacent if and only if $g^{-1}\alpha (g)\notin Z(G)$. In this paper, we investigate some fundamental properties of ${\mathrm{\Gamma }}_G$ such as connectivity, diameter, girth, Hamiltonian, independence and dominating numbers. Moreover, planarity and outer planarity of the graph are studied.

A 2-factorization {F₁, F₂,…,F_d} of a 2d-regular graph G such that each and the remaining F_i's are all Hamilton cycles is called Hamilton cycle rich 2-factorization of G, where G_i's are the given non-isomorphic 2-factors of G. In this paper, we prove that there exists a 2-factorization {F₁, F₂,…,F_n} of K_2n,2n such that F₁ ≅ G₁, F₂ ≅ G₂ and the remaining F_i's are Hamilton cycles of K_2n,2n, where G₁ and G₂ are the given two non-isomorphic 2-factors of K_2n,2n. In fact our result together with the earlier results settles the existence of Hamilton cycle rich 2-factorizations of K(m, p), the complete p-partite graph with m vertices in each partite set, except when (m, p) = (2n + 1, 2), in the case that two of the 2-factors are isomorphic to the given two non-isomorphic 2-factors and the remaining are Hamilton cycles.

In this paper, we study the signed $k$-domination and its total version in graphs. By a simple uniform approach we give some new upper and lower bounds on these two parameters of a graph in terms of several different graph parameters. In this way, we can improve and generalize some results in literature. Moreover, we make use of the well-known theorem of Turán [On an extremal problem in graph theory, Math. Fiz. Lapok48 (1941) 436–452] to bound the signed total $k$-domination number, ${\gamma }_{kS}^t(G)$, of a $K_{r+1}$-free graph $G$ for $r\ge 2$.

We consider the maximum 1-2 matching problem in bipartite graphs. The notion of the augmenting trail for the 1-2 matching problem, which is the extension of the notion of the augmenting path for the 1-1 matching problem is introduced. The main purpose of the present paper is to prove “the augmenting trail theorem” for the 1-2 matching problem in the bipartite graph, which is an analogue of the augmenting path theorem by Bergé for the usual 1-1 matching problems.