Search

This article introduces difference distance magic (DDM) labelings, a new labeling on oriented graphs. We discuss basic properties of oriented graphs that have a DDM labeling and methods for constructing DDM labelings in a wide variety of oriented graph classes. We also give a variety of oriented graph classes that fail to produce a DDM labeling. [ABSTRACT FROM AUTHOR]

Given a pair of real symmetric matrices A , B ∈ R n × n with nonzero patterns determined by the edges of any pair of chosen graphs on n vertices, we consider an inverse eigenvalue problem for the structured matrix C = [ A B I O ] ∈ R 2 n × 2 n. We conjecture that C can attain any spectrum that is closed under conjugation. We use a structured Jacobian method to prove this conjecture for A and B of orders at most 4 or when the graph of A has a Hamilton path, and prove a weaker version of this conjecture for any pair of graphs with a restriction on the multiplicities of eigenvalues of C. [ABSTRACT FROM AUTHOR]

The relative fixity of a digraph Γ is defined as the ratio between the largest number of vertices fixed by a nontrivial automorphism of Γ and the number of vertices of Γ . We characterize the vertex-primitive digraphs whose relative fixity is at least 1 3 , and we show that there are only finitely many vertex-primitive digraphs of bounded out-valency and relative fixity exceeding a positive constant. [ABSTRACT FROM AUTHOR]

A digraph H $H$ is called ubiquitous if every digraph D $D$ that contains k $k$ vertex‐disjoint copies of H $H$ for every k∈N $k\in {\mathbb{N}}$ also contains infinitely many vertex‐disjoint copies of H $H$. We characterise which digraphs with rays as underlying undirected graphs are ubiquitous. [ABSTRACT FROM AUTHOR]

A finite-time consensus protocol is presented in this paper for a network of connected heterogeneous agents with fixed and switching topology. In this study, two cases directed networks with fixed topology and directed networks with switching topology are examined. Convergence analysis for both the cases are presented. An independent tracking controller, which assures that an agent follows an ideal trajectory designed by sliding mode based consensus control, is devised. Agents stability are independent of the distributed consensus algorithm. Under the proposed control methodology, the measurement vectors of heterogeneous agents converge to the agreement value in a finite amount of time. The comparison results with the existing works show the proposed algorithm's improved performance in terms of convergence time in presence of disturbances. [ABSTRACT FROM AUTHOR]

We investigate a proper arc colouring of oriented graphs such that for each vertex the colours of all out-arcs incident with the vertex and the colours of all in-arcs incident with the vertex form intervals of integers. Oriented graphs having such colourings are called interval colourable. We analyse the parameter icr (D) , which denotes the minimum number of arcs of D that should be reversed so that a resulting oriented graph is interval colourable. We prove that for each non-negative integer p there exists an oriented graph D with the property p ≤ icr (D) ≤ 4 p + 1. We show that icr (D) is not monotone with respect to taking subdigraphs. We give an upper bound on icr (D) if D is an arbitrary oriented graph with finite parameter icr (D) , and next if D is any orientation of a 2-degenerate graph. Also the exact values of icr (D) for all orientations D of some generalized Hertz graphs and generalized Sevastjanov rosettes are given. Based on special results concerning the still open problem of finding the largest possible transitive subtournament in a tournament (posed by Erdős and Moser in 1964) we refine the upper bound on icr (D) if D is a tournament. [ABSTRACT FROM AUTHOR]

The stable index of a 0–1 matrix A is defined to be the smallest integer k such that $ A^{k+1} $ A k + 1 is not a 0–1 matrix if such an integer exists; otherwise the stable index of A is defined to be infinity. We characterize the set of stable indices of 0–1 matrices with a given order. [ABSTRACT FROM AUTHOR]

In this paper, we extend the definition of cohomology associated to monotone graph properties, to encompass twisted functor coefficients. We introduce oriented matchings on graphs, and focus on their (twisted) cohomology groups. We characterise oriented matchings in terms of induced free-flow pseudoforests, and explicitly determine the homotopy type of the associated simplicial complexes. Furthermore, we provide a connection between the cohomology of oriented matchings with certain functor coefficients, and the recently defned multipath cohomology. Finally, we define a further oriented homology for graphs and interpret it as a count of free-fow orientations. [ABSTRACT FROM AUTHOR]

This paper describes several cases of adjunction in the homomorphism preorder of relational structures. We say that two functors Λ and Γ between thin categories of relational structures are adjoint if for all structures A and B, we have that Λ⁢(A) maps homomorphically to B if and only if A maps homomorphically to Γ⁢(𝐁). If this is the case, Λ is called the left adjoint to Γ and Γ the right adjoint to Λ. In 2015, Foniok and Tardif described some functors on the category of digraphs that allow both left and right adjoints. The main contribution of Foniok and Tardif is a construction of right adjoints to some of the functors identified as right adjoints by Pultr in 1970. We generalise results of Foniok and Tardif to arbitrary relational structures, and coincidently, we also provide more right adjoints on digraphs, and since these constructions are connected to finite duality, we also provide a new construction of duals to trees. Our results are inspired by an application in promise constraint satisfaction -- it has been shown that such functors can be used as efficient reductions between these problems. [ABSTRACT FROM AUTHOR]

A digraph G $G$ is k $k$‐geodetic if for any (not necessarily distinct) vertices u,v $u,v$ there is at most one directed walk from u $u$ to v $v$ with length not exceeding k $k$. The order of a k $k$‐geodetic digraph with minimum out‐degree d $d$ is bounded below by the directed Moore bound M(d,k)=1+d+d2+⋯+dk $M(d,k)=1+d+{d}^{2}+\cdots +{d}^{k}$. The Moore bound can be met only in the trivial cases d=1 $d=1$ and k=1 $k=1$, so it is of interest to look for k $k$‐geodetic digraphs with out‐degree d $d$ and smallest possible order M(d,k)+ϵ $M(d,k)+{\epsilon }$, where ϵ ${\epsilon }$ is the excess of the digraph. Miller, Miret and Sillasen recently ruled out the existence of digraphs with excess one for k=3,4 $k=3,4$ and d≥2 $d\ge 2$ and for k=2 $k=2$ and d≥8 $d\ge 8$. We conjecture that there are no digraphs with excess one for d,k≥2 $d,k\ge 2$ and in this paper we investigate the structure of minimal counterexamples to this conjecture. We severely constrain the possible structures of the outlier function and prove the nonexistence of certain digraphs with degree three and excess one, as well closing the open cases k=2 $k=2$ and d=3,4,5,6,7 $d=3,4,5,6,7$ left by the analysis of Miller et al. We further show that there are no involutary digraphs with excess one, that is, the outlier function of any such digraph must contain a cycle of length ≥3 $\ge 3$. [ABSTRACT FROM AUTHOR]

A tournament is an orientation of a graph. Each edge is a match, directed towards the winner. The score sequence lists the number of wins by each team. In this article, by interpreting score sequences geometrically, we generalize and extend classical theorems of Landau (Bull. Math. Biophys. 15, 143–148 (1953)) and Moon (Pac. J. Math. 13, 1343–1345 (1963)), via the theory of zonotopal tilings. [ABSTRACT FROM AUTHOR]

The dichromatic number ...(D) of a digraph D is the least integer k such that D can be partitioned into k directed acyclic digraphs. A digraph is k-dicritical if ...(D) = k and each proper subgraph D' of D satisfies ...(-D') ≤ k - 1. An oriented graph is a digraph with no directed cycle of length 2. For integers k and n, we denote by Ok(n) the minimum number of edges of a k-dicritical oriented graph on n vertices. The main result of this paper is a proof that O3(n) ≥ 7n+2/3 together with a construction witnessing that O3(n) ≤ ⌈5n/2⌉ for all n ≥ 12. We also give a construction showing that for all sufficiently large n and all k ≥ 3, Ok(n) < (2k -- 3)n, disproving a conjecture of Hoshino and Kawarabayashi. [ABSTRACT FROM AUTHOR]

In this paper we prove the following new sufficient condition for a digraph to be Hamiltonian: Let D be a 2-strong digraph of order n ≥ 9. If n − 1 vertices of D have degrees at least n + k and the remaining vertex has degree at least n − k − 4, where k is a non-negative integer, then D is Hamiltonian. This is an extension of Ghouila-Houri’s theorem for 2-strong digraphs and is a generalization of an early result of the author (DAN Arm. SSR (91(2):6-8, 1990). The obtained result is best possible in the sense that for k = 0 there is a digraph of order n = 8 (respectively, n = 9) with the minimum degree n − 4 = 4 (respectively, with the minimum degree n − 5 = 4) whose n − 1 vertices have degrees at least n − 1, but it is not Hamiltonian. We also give a new sufficient condition for a 3-strong digraph to be Hamiltonian-connected. [ABSTRACT FROM AUTHOR]

Let k = 1 be an integer, and let D be a finite and simple digraph with vertex set V (D). A weak signed Roman k-dominating function (WSRkDF) on a digraph D is a function f: V (D) {-1, 1, 2} satisfying the condition that P xN-[v] f(x) = k for each v V (D), where N-[v] consists of v and all vertices of D from which arcs go into v. The weight of a WSRkDF f is w(f) = P vV (D) f(v). The weak signed Roman k-domination number kw sR(D) is the minimum weight of a WSRkDF on D. In this paper we initiate the study of the weak signed Roman k-domination number of digraphs, and we present different bounds on kw sR(D). In addition, we determine the weak signed Roman k-domination number of some classes of digraphs. Some of our results are extensions of well-known properties of the weak signed Roman domination number wsR(D) = 1w sR(D) and the signed Roman k-domination number k sR(D). [ABSTRACT FROM AUTHOR]

Let \(k\geq 1\) be an integer, and let \(D\) be a finite and simple digraph with vertex set \(V(D)\). A weak signed Roman \(k\)-dominating function (WSRkDF) on a digraph \(D\) is a function \(f \colon V(D)\rightarrow \{-1,1,2\}\) satisfying the condition that \(\sum_{x \in N^-[v]}f(x)\geq k\) for each \(v\in V(D)\), where \(N^-[v]\) consists of \(v\) and all vertices of \(D\) from which arcs go into \(v\). The weight of a WSRkDF \(f\) is \(w(f)=\sum_{v\in V(D)}f(v)\). The weak signed Roman \(k\)-domination number \(\gamma_{wsR}^k(D)\) is the minimum weight of a WSRkDF on \(D\). In this paper we initiate the study of the weak signed Roman \(k\)-domination number of digraphs, and we present different bounds on \(\gamma_{wsR}^k(D)\). In addition, we determine the weak signed Roman \(k\)-domination number of some classes of digraphs. Some of our results are extensions of well-known properties of the weak signed Roman domination number \(\gamma_{wsR}(D)=\gamma_{wsR}^1(D)\) and the signed Roman \(k\)-domination number \(\gamma_{sR}^k(D).\)

Tropical cyclone (TC)‐induced remote moisture transport is the fundamental cause of TC‐induced remote precipitation. However, despite increasing attention having been paid to TC‐induced remote moisture transport over the past few decades, a method for the objective identification of TC remote moisture transport remains lacking, which is crucial to understanding the complex rainfall mechanisms associated with TC‐induced remote moisture transport over recent decades. We set out to solve this issue in the present study by using a series of newly developed processing algorithms. Firstly, we identified vertically integrated water vapour transport (IVT) pathways using spatially smoothed moving window quantiles, and then used the maximum gradient method to segment IVT clusters from pathways. Relationship digraphs were constructed for IVT clusters to flexibly interpret the spatio‐temporal merging and splitting processes among them. Finally, TC clusters (TCCs) and TC remote clusters (TRCs) were identified in succession based on the TC tracks and diagraphs of IVT clusters. Applications of these processing algorithms showed that the TCCs and TRCs at the same time step can be identified successfully by applying our method. The generality of the objective identification method was validated using data covering four decades. Our algorithms revealed discontinuous and uneven moisture transport, especially those associated with TCs, which benefits studies of remote rainfall associated with TCs. Furthermore, it facilitates the construction of IVT pathway and cluster datasets covering the past several decades, which can be used for analysing related characteristics and thereby revealing possible physical mechanisms underlying the nature of TRCs. [ABSTRACT FROM AUTHOR]

We prove that for every ε > 0 there exists n 0 = n 0 (ε) such that every regular oriented graph on n > n 0 vertices and degree at least (1 / 4 + ε) n has a Hamilton cycle. This establishes an approximate version of a conjecture of Jackson from 1981. We also establish a result related to a conjecture of Kühn and Osthus about the Hamiltonicity of regular directed graphs with suitable degree and connectivity conditions. [ABSTRACT FROM AUTHOR]

We focus upon the reciprocal matrix component of the often discussed Analytic Hierarchy Process and its approximation by a consistent matrix formed from an efficient vector. It is known that a vector is efficient for a reciprocal matrix A if and only if a certain digraph is strongly connected. Here, we give a transparent and relatively simple matricial proof of this important result. Then we show that any Hadamard weighted geometric mean of the columns of a reciprocal matrix is efficient. This is a major generalization of the known result that the Hadamard geometric mean of all columns is efficient, and of the recent result that the geometric mean of any subset of the columns is efficient. [ABSTRACT FROM AUTHOR]

In this article, motivated by a problem of Scott [Surveys in combinatorics, 327 (2005), 95-117.] and a conjecture of Lee et al. [Random Struct. Algorithm, 48 (2016), 147-170.] we consider bisections of directed graphs. We prove that every directed graph with m arcs and minimum semidegree at least d admits a bisection in which at least (d/2(2d+1) + o(1)) m arcs cross in each direction. This provides an optimal bound as well as a positive answer to a question of Hou and Wu [J. Comb. Theory B, 132 (2018), 107-133.] in a stronger form. [ABSTRACT FROM AUTHOR]

The study aimed in identifying Green supply chain critical success factors, develop and validate the framework through integrated approach of ISM, MICMAC and SEM so as to promote green practices throughout the supply chain activities in Indian manufacturing sectors. Interpretive structural modelling(ISM) is applied to develop hierarchical contextual relationship among identified critical success factors via Pareto analysis. The methodology then follows classification of success factors into four clusters by Matrice d’ Impacts Croisés-Multiplication Appliquée á un Classement (MICMAC) and statistical validation of the ISM model through Structural Equation Modelling(SEM) by AMOS. In this study, 16 critical success factors of Green supply chain practices for manufacturing industries were identified, followed by development of an ISM model using 16 critical success factors, later the model was statistically verified that identified nine CSF’s responsible for generating SEM model by satisfying all the model fit indices.The linkage variables identified are Green manufacturing, Green Procurement, Green marketing and Distribution, Green purchasing, Supplier cooperation, Customer cooperation, Environmental strategies and management, Environmental Participation and Green training that are forming the driving force for practicing green supply chain. Research limitations/implications: The results of the study are restricted to manufacturing industries, which might vary when applied for other sectors. The developed model on green supply chain management practices would help policy makers, decision makers, researchers and industry professionals to anticipate potential success factors to implement green supply chain practices. Accordingly, the focus on critical success factors would be prioritized for obtaining better performance of supply chain and greening the chain.

Copyright of Pulchra Lingua: A Journal of Language Study, Literature & Linguistics is the property of Pulchra Lingua: A Journal of Language Study, Literature & Linguistics and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The Wiener index of a strong digraph D is defined as the sum of the shortest path distances between all ordered pairs of vertices. This definition has been extended to digraphs that are not necessarily strong by defining the distance from a vertex a to a vertex b as 0 if there is no path from a to b in D. Knor et al. (2016) [9] considered (not necessarily strong) orientations of graphs with maximum Wiener index. The authors conjectured that for a given tree T , an orientation D of T of maximum Wiener index always contains a vertex v such that for every vertex u , there is either a (u , v) -path or a (v , u) -path in D. In this paper we disprove the conjecture. We also show that the problem of finding an orientation of maximum Wiener index of a given graph is NP-complete, thus answering a question by Knor et al. (2016) [8]. We briefly discuss the corresponding problem of finding an orientation of minimum Wiener index of a given graph, and show that the special case of deciding if a given graph on m edges has an orientation of Wiener index m can be solved in time quadratic in the order of the graph. [ABSTRACT FROM AUTHOR]

The bitopologies have been associated with some knots in the literature with the help of a method called the knot digraph notation. The knot graphs and quasi pseudo metric spaces were used to obtain these bitopologies. With the help of quasi pseudo metrics, two topologies were obtained on a set. In this way, an association between some knots and bitopologies was established. The authors sought an answer to the question "Given the bitopologies associated with knots, can the knot itself be obtained ?" and they gave a method. This mentioned method consists of 6 steps. In this work, it is shown in detail that according to the Alexander-Briggs notation, the reverse of the knot digraph notation is provided for the knots 31, 51, 52, 61, 62, 71, 72, 73, 81, 82, 83, 91, 92, 93, 101, 102, 103. [ABSTRACT FROM AUTHOR]

Let D be a finite and simple digraph with vertex set V(D). A signed total Italian dominating function (STIDF) on a digraph D is a function f:V(D)→{-1,1,2} satisfying the conditions that (i) ∑x∈N-(v)f(x)≥1 for each v∈V(D), where N-(v) consists of all vertices of D from which arcs go into v, and (ii) every vertex u for which f(u)=-1 has an in-neighbor v for which f(v)=2 or two in-neighbors w and z with f(w)=f(z)=1. The weight of an STIDF f is ∑v∈V(D)f(v). The signed total Italian domination number γstI(D) of D is the minimum weight of an STIDF on D. In this paper we initiate the study of the signed total Italian domination number of digraphs, and we present different bounds on γstI(D). In addition, we determine the signed total Italian domination number of some classes of digraphs. [ABSTRACT FROM AUTHOR]

A new alternative model for expressing more complex knowledge has been proposed as an attributed predicate RDF (APRDF). By handling attributes that represent any additional triples of the main triple, APRDF serves as a predicate. Therefore, the formal graph model of APRDF must be defined. Lastly, this work recommends that the APRDF's conventional diagram is a digraphhypergraph mix. The previous formal graph of RDF is a hypergraph even though, visually intuitively, it is a digraph. It also contains inconsistency. The other new serialization needs to describe its formal model. Eventually, this work can provide the formal graph model of APRDF and maintain consistency. There have been a few definitions proposed. The direct impact of this formal model is that APRDF outperformed the other model significantly when retrieving complex queries within its formal graph. In querying, the initial implementation of the proposed formal graph takes an average of 62 milliseconds. Compared to the other graph models, the proposed formal graph can reduce query time by an average of 90,7 milliseconds on the BF-arch graph and 121,05 milliseconds on the naive/default graph. As the formal graph model is preserved, the attributed predicate of APRDF assumed will drive a new model in the retrieving process that more in using a predicate formed as a link in a graph. It will also be impacted in the mining process by more elaborate links/edges (link mining). [ABSTRACT FROM AUTHOR]

We introduce the following cycle selection problem which is motivated by an application to kidney exchange problems. Given a directed graph G = (V , A) , a cycle selection is a subset of arcs B ⊆ A forming a union of directed cycles. A related optimization problem, the Maximum Weighted Cycle Selection problem can be defined as follows: given a weight w i , j ∈ R for all arcs (i , j) ∈ A , find a cycle selection B which maximizes w (B). We prove that this problem is strongly NP-hard. Next, we focus on cycle selections in complete directed graphs. We provide several ILP formulations of the problem: an arc formulation featuring an exponential number of constraints which can be separated in polynomial time, four extended compact formulations, and an extended non compact formulation. We investigate the relative strength of these formulations. We concentrate on the arc formulation and on the description of the associated cycle selection polytope. We prove that this polytope is full-dimensional, and that all the inequalities used in the arc formulation are facet-defining. Furthermore, we describe three new classes of facet-defining inequalities and a class of valid inequalities. We also consider the consequences of including additional constraints on the cardinality of a selection or on the length of the associated cycles. [ABSTRACT FROM AUTHOR]

A tournament on a graph is an orientation of its edges. The score sequence lists the in-degrees in non-decreasing order. Works by Winston and Kleitman (J Comb Theory Ser A 35(2):208–230, 1983) and Kim and Pittel (J Comb Theory Ser A 92(2):197–206, 2000) showed that the number S n of score sequences on the complete graph K n satisfies S n = Θ (4 n / n 5 / 2) . By combining a recent recurrence relation for S n in terms of the Erdős–Ginzburg–Ziv numbers N n with the limit theory for discrete infinitely divisible distributions, we observe that n 5 / 2 S n / 4 n → e λ / 2 π , where λ = ∑ k = 1 ∞ N k / k 4 k . This limit agrees numerically with the asymptotics of S n conjectured by Takács (J Stat Plan Inference 14(1):123–142, 1986). We also identify the asymptotic number of strong score sequences, and show that the number of irreducible subscores in a random score sequence converges in distribution to a shifted negative binomial with parameters r = 2 and p = e - λ . [ABSTRACT FROM AUTHOR]

We analyze the existence of coincidence points for graph preserving hybrid pair of mappings in controlled metric type spaces. Our results extend and generalize several recent fixed point results including the well-known Nadler's fixed point theorem. Finally, we provide some examples to illustrate and justi fy the validity of our main result. [ABSTRACT FROM AUTHOR]

Let G:= (V, E) be a digraph. The subdigraph of G induced by a subset X of V is denoted by G[X]. The dual of G, denoted by G*, is the digraph obtained from G by reversing all its arcs. A digraph G':= (V', E') is hemimorphic to G if G and G' are isomorphic or G* and G' are isomorphic. Given a nonnegative integer k, a digraph G' defined on V is (= k)-hemimorphic to G if for every subset X of V with at most k elements, the subdigraphs G[X] and G' [X] are hemimorphic. A digraph G' defined on V is hereditarily hemimorphic to G, if for every subset X of V, the subdigraphs G[X] and G' [X] are hemimorphic. The digraph G is (= k)-hereditarily-half reconstructible, whenever each digraph G' (= k)-hemimorphic to G, is hereditarily hemimorphic to it. In this paper we answer Y. Boudabbous's question by characterizing the (= k)-hereditarily half-reconstructible digraphs, for each integer k such that k = 7. [ABSTRACT FROM AUTHOR]

In this article the (weakly) sign symmetric [(w)ss] Q1-matrix completion problems are studied. Some necessary and sufficient conditions for a digraph to have (weakly) sign symmetric Q1-completion are shown. Lastly the digraphs of order at most four having (w)ss Q1-completion have been sorted out. [ABSTRACT FROM AUTHOR]

The study aimed in identifying Green supply chain critical success factors, develop and validate the framework through integrated approach of ISM, MICMAC and SEM so as to promote green practices throughout the supply chain activities in Indian manufacturing sectors. Interpretive structural modelling(ISM) is applied to develop hierarchical contextual relationship among identified critical success factors via Pareto analysis. The methodology then follows classification of success factors into four clusters by Matrice d’ Impacts Croisés-Multiplication Appliquée á un Classement (MICMAC) and statistical validation of the ISM model through Structural Equation Modelling(SEM) by AMOS. In this study, 16 critical success factors of Green supply chain practices for manufacturing industries were identified, followed by development of an ISM model using 16 critical success factors, later the model was statistically verified that identified nine CSF’s responsible for generating SEM model by satisfying all the model fit indices.The linkage variables identified are Green manufacturing, Green Procurement, Green marketing and Distribution, Green purchasing, Supplier cooperation, Customer cooperation, Environmental strategies and management, Environmental Participation and Green training that are forming the driving force for practicing green supply chain. Research limitations/implications: The results of the study are restricted to manufacturing industries, which might vary when applied for other sectors. The developed model on green supply chain management practices would help policy makers, decision makers, researchers and industry professionals to anticipate potential success factors to implement green supply chain practices. Accordingly, the focus on critical success factors would be prioritized for obtaining better performance of supply chain and greening the chain. [ABSTRACT FROM AUTHOR]

The basic purpose of this article is to introduce the concept of R-γ-G-contraction by using R-functions, lower semi-continuous functions and digraphs and discuss the existence and uniqueness of points of coincidence and common fixed points for a pair of self-mappings satisfying such contractions in the setting of metric spaces endowed with a graph. As some consequences of our results, we obtain several recent results in metric spaces and partial metric spaces. [ABSTRACT FROM AUTHOR]

Copyright of Problems of Mechatronics. Armament, Aviation, Safety Engineering / Problemy Mechatroniki. Uzbrojenie, lotnictwo, Inżynieria Bezpieczeństwa is the property of Index Copernicus International and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Given a digraph D, the complementarity spectrum of the digraph is defined as the set of complementarity eigenvalues of its adjacency matrix. This complementarity spectrum has been shown to be useful in several fields, particularly in spectral graph theory. The differences between the properties of the complementarity spectrum for (undirected) graphs and for digraphs make the study of the latter of particular interest, and characterizing strongly connected digraphs with a small number of complementarity eigenvalues is a nontrivial problem. Recently, strongly connected digraphs with one and two complementarity eigenvalues have been completely characterized. In this paper, we study strongly connected digraphs with exactly three elements in the complementarity spectrum, ending with a complete characterization. This leads to a structural characterization of general digraphs having three complementarity eigenvalues. [ABSTRACT FROM AUTHOR]

AbstractGraph partitioning problem, which is one of the most important topics in graph theory, usually asks for a partition of the vertex set of a graph into pairwise disjoint subsets with various requirements. It comes from the well-known Max-Cut Problem: Given a graph G, find the maximum bipartite subgraph of G. In practice, one often needs to find a partition of a given graph to optimize several quantities simultaneously. Such problems are called judicious partition problems by Bollobás and Scott. In this survey, we present some new results and problems on graph partitioning.