Academic literature on the topic 'Quasi-Bipartite graph'

In this paper, we study some graph-theoretic properties about the zero-divisor graph [Formula: see text] of a finite quasi-ordered set [Formula: see text] with a least element 0 and its line graph [Formula: see text]. First, we offer a method to find all the minimal prime ideals of a quasi-ordered set. Especially, this method is applicable for a partially ordered set. Then, we completely characterize the diameter and girth of [Formula: see text] by the minimal prime ideals of [Formula: see text]. Besides, we perfectly classify all finite quasi-ordered sets whose zero-divisor graphs are complete graphs, star graphs, complete bipartite graphs, complete [Formula: see text]-partite graphs. We also investigate the planarity of [Formula: see text]. Finally, we obtain the characterization for the line graph [Formula: see text] in terms of its diameter, girth and planarity.

Let M be a module over a commutative ring R. In this paper, we continue our study about the quasi-Zariski topology-graph G(?*T) which was introduced in (On the graph of modules over commutative rings, Rocky Mountain J. Math. 46(3) (2016), 1-19). For a non-empty subset T of Spec(M), we obtain useful characterizations for those modules M for which G(?*T) is a bipartite graph. Also, we prove that if G(?*T) is a tree, then G(?*T) is a star graph. Moreover, we study coloring of quasi-Zariski topology-graphs and investigate the interplay between ?(G(?+T)) and ?(G(?+T)).

This work is aimed to introduce a new topology on a graph, namely the degree topology. This topology is defined by the degree of the vertices of the graphs. We find the degree topology for certain types of graphs and determine their types. The degree topology for the complete graph is an indiscrete topology. While The degree topology is generated by a complete bipartite graph with is a quasi-discrete topology. In addition, a new property is initiated namely set- space and discussed the link between it and space. We verify that every degree topology is a set- space.

Let G be a connected non-regular non-bipartite graph whose adjacency matrix has spectrum p,?(k),?(l), where k,l ? N and p > ? > ?. We show that if ? is non-main then ?(G) ? 1 + ? - ??, with equality if and only if G is of one of three types, derived from a strongly regular graph, a symmetric design or a quasi-symmetric design (with appropriate parameters in each case).

LetGbe an undirected simple graph of ordern. LetA(G)be the adjacency matrix ofG, and letμ1(G)≤μ2(G)≤⋯≤μn(G)be its eigenvalues. The energy ofGis defined asℰ(G)=∑i=1n‍|μi(G)|. Denote byGBPTa bipartite graph. In this paper, we establish the sufficient conditions forGhaving a Hamiltonian path or cycle or to be Hamilton-connected in terms of the energy of the complement ofG, and give the sufficient condition forGBPThaving a Hamiltonian cycle in terms of the energy of the quasi-complement ofGBPT.

The Steiner tree problem (STP) aims to determine some Steiner nodes such that the minimum spanning tree over these Steiner nodes and a given set of special nodes has the minimum weight, which is NP-hard. STP includes several important cases. The Steiner tree problem in graphs (GSTP) is one of them. Many heuristics have been proposed for STP, and some of them have proved to be performance guarantee approximation algorithms for this problem. Since evolutionary algorithms (EAs) are general and popular randomized heuristics, it is significant to investigate the performance of EAs for STP. Several empirical investigations have shown that EAs are efficient for STP. However, up to now, there is no theoretical work on the performance of EAs for STP. In this article, we reveal that the (1+1) EA achieves 3/2-approximation ratio for STP in a special class of quasi-bipartite graphs in expected runtime [Formula: see text], where [Formula: see text], [Formula: see text], and [Formula: see text] are, respectively, the number of Steiner nodes, the number of special nodes, and the largest weight among all edges in the input graph. We also show that the (1+1) EA is better than two other heuristics on two GSTP instances, and the (1+1) EA may be inefficient on a constructed GSTP instance.

This paper proposes a new variant of multi-play MAB model, to capture important factors of the sequential user-centric selection problem arising from mobile edge computing, ridesharing applications, etc. In the proposed model, each arm is associated with discrete units of resources, each play is associate with movement costs and multiple plays can pull the same arm simultaneously. To learn the optimal action profile (an action profile prescribes the arm that each play pulls), there are two challenges: (1) the number of action profiles is large, i.e., M^K, where K and M denote the number of plays and arms respectively; (2) feedbacks on action profiles are not available, but instead feedbacks on some model parameters can be observed. To address the first challenge, we formulate a completed weighted bipartite graph to capture key factors of the offline decision problem with given model parameters. We identify the correspondence between action profiles and a special class of matchings of the graph. We also identify a dominance structure of this class of matchings. This correspondence and dominance structure enable us to design an algorithm named OffOptActPrf to locate the optimal action efficiently. To address the second challenge, we design an OnLinActPrf algorithm. We design estimators for model parameters and use these estimators to design a Quasi-UCB index for each action profile. The OnLinActPrf uses OffOptActPrf as a subroutine to select the action profile with the largest Quasi-UCB index. We conduct extensive experiments to validate the efficiency of OnLinActPrf.

In the hybrid communication scenario of the Heterogeneous Cloud Radio Access Network and Device-to-Device in 5G, spectrum efficiency promotion and the interference controlling caused by spectrum reuse are still challenges. In this article, a novel resource management method, consisting of power and channel allocation, is proposed to solve this problem. An optimization model to maximum the system throughput and spectrum efficiency of the system, which is constrained by Signal to Interference plus Noise Ratio requirements of all users in diverse layers, is established. To solve the non-convex mixed integer nonlinear optimization problem, the optimization model is decomposed into two sub-problems, which are all solvable quasi-convex power allocation and non-convex channel allocation. The first step is to solve a power allocation problem based on solid geometric programming with the vertex search method. Then, a channel allocation constructed by three-dimensional hypergraph matching is established, and the best result of this problem is obtained by a heuristic greed algorithm based on the bipartite conflict graph and µ-claw search. Finally, the simulation results show that the proposed scheme improves the throughput performance at least 6% over other algorithms.

Dans cette thèse, nous étudions les polyèdres total dual box-intègraux (box-TDI) associés à plusieurs problèmes et matrices totalement équimodulaires. De plus, nous étudions la complexité de certaines questions fondamentales liées à ces polyèdres. Nous commençons par considérer les matrices totalement équimodulaires, qui sont des matrices telles que, pour chaque sous-ensemble de lignes linéairement indépendantes, toutes les sous-matrices maximales non-singulières ont le même déterminant en valeur absolue. Malgré leurs similitudes avec les matrices totalement unimodulaires, nous mettons en évidence plusieurs différences, même dans le cas des matrices d'incidence et d'adjacence des graphes. Comme on le sait, la matrice d'incidence d'un graphe donné est totalement unimodulaire si et seulement si le graphe est biparti. Cependant, la totale équimodularité d'une matrice d'incidence dépend du fait que nous considérons la représentation sommet-arête ou arête-sommet. Nous fournissons des caractérisations pour les deux cas. En conséquence, nous prouvons que reconnaître si un polyèdre donné est box-TDI est un problème co-NP-complet. La caractérisation de la totale unimodularité ou de la totale équimodularité de la matrice d'adjacence d'un graphe biparti donné reste non résolue, alors que nous avons résolu le problème correspondant dans le cas de la totale équimodularité lorsque le graphe est non-biparti. Dans une dernière partie, nous caractérisons les graphes pour lesquels le polytope des couplages parfaits (PMP) est décrit par des inégalités triviales et des inégalités correspondant à des coupes serrées. Les coupes serrées sont définies comme des coupes qui partagent précisément une arête avec chaque couplage parfait. Nous prouvons ensuite que tout graphe pour lequel le PMP correspondant est box-TDI appartient à cette classe. En conséquence, reconnaître si le PMP est box-TDI est un problème résoluble en temps polynomial. Cependant, nous fournissons plusieurs contre-exemples montrant que cette classe de graphes ne garantit pas la box-TDIness du PMP. Enfin, nous présentons des conditions nécessaires pour un polytope de couverture des arêtes pour être box-TDI et caractérisons quand le polytope des couplages extensibles est box-TDI, qui est l'enveloppe convex des couplages inclus dans un couplage parfait
In this thesis, we study box-totally dual integral (box-TDI) polyhedra associated with severalproblems and totally equimodular matrices. Moreover, we study the complexity of some funda-mental questions related to them.We start by considering totally equimodular matrices, which are matrices such that, forevery subset of linearly independent rows, all nonsingular maximal submatrices have the samedeterminant in absolute value. Despite their similarities with totally unimodular matrices, wehighlight several differences, even in the case of incidence and adjacency matrices of graphs.As is well-known, the incidence matrix of a given graph is totally unimodular if and only if thegraph is bipartite. However, the total equimodularity of an incidence matrix depends on whetherwe consider the vertex-edge or the edge-vertex representation. We provide characterizations forboth cases. As a consequence, we prove that recognizing whether a given polyhedron is box-TDIis a co-NP-complete problem.Characterizing the total unimodularity or total equimodularity of the adjacency matrix of agiven bipartite graph remains unsolved, while we solved the corresponding problem in the case oftotal equimodularity when the graph is nonbipartite.In a later part of this work, we characterize the graphs for which the perfect matching polytope(PMP) is described by trivial inequalities and the inequalities corresponding to tight cuts. Tightcuts are defined as cuts that share precisely one edge with each perfect matching. We thenprove that any graph for which the corresponding PMP is box-TDI belongs to this class. Asa consequence, it turns out that recognizing whether the PMP is box-TDI is a polynomial-timeproblem. However, we provide several counterexamples showing that this class of graphs does notguarantee the box-TDIness of the PMP.Lastly, we present necessary conditions for the box-TDIness of the edge cover polytope andcharacterize the box-TDIness of the extendable matching polytope, which is the convex hull ofthe matchings included in a perfect matching