Search

Let G and H be two graphs, each one of them being a path, a cycle or a star. In this paper, we determine the b-chromatic number of every subdivision-vertex neighbourhood corona G H or G Kn, where Kn is the complete graph of order n. It is also established for those graphs Kn G having m-degree not greater than n + 2. All the proofs are accompanied by illustrative examples.

For a drawing of a labeled graph, the rotation of a vertex or crossing is the cyclic order of its incident edges, represented by the labels of their other endpoints. The extended rotation system (ERS) of the drawing is the collection of the rotations of all vertices and crossings. A drawing is simple if each pair of edges has at most one common point. Gioan’s Theorem states that for any two simple drawings of the complete graph K_n with the same crossing edge pairs, one drawing can be transformed into the other by a sequence of triangle flips (a.k.a. Reidemeister moves of Type 3). This operation refers to the act of moving one edge of a triangular cell formed by three pairwise crossing edges over the opposite crossing of the cell, via a local transformation. We investigate to what extent Gioan-type theorems can be obtained for wider classes of graphs. A necessary (but in general not sufficient) condition for two drawings of a graph to be transformable into each other by a sequence of triangle flips is that they have the same ERS. As our main result, we show that for the large class of complete multipartite graphs, this necessary condition is in fact also sufficient. We present two different proofs of this result, one of which is shorter, while the other one yields a polynomial time algorithm for which the number of needed triangle flips for graphs on n vertices is bounded by O(n^{16}). The latter proof uses a Carathéodory-type theorem for simple drawings of complete multipartite graphs, which we believe to be of independent interest. Moreover, we show that our Gioan-type theorem for complete multipartite graphs is essentially tight in the following sense: For the complete bipartite graph K_{m,n} minus two edges and K_{m,n} plus one edge for any m,n ≥ 4, as well as K_n minus a 4-cycle for any n ≥ 5, there exist two simple drawings with the same ERS that cannot be transformed into each other using triangle flips. So having the same ERS does not remain sufficient when

This paper studies synchronization of a network of hybrid quadratic integrate-and-fire spiking neurons communicating over a complete graph and interconnected by means of bidirectional electrical couplings. Synchronization of the network of identical neurons with a common and constant coupling strength is studied using a Lyapunov-based argument for sufficiently large coupling strength. In addition, a voltage-dependent coupling law is proposed. It is assumed that each neuron is coupled to each of its neighbors by a coupling law which depends on the voltage of its neighboring neuron. For the voltage-dependent case, a sufficient condition for synchronization of two interconnected neurons is presented. Moreover, a comparison between the two mechanisms is given. Simulation results are provided to verify the theoretical analysis., QC 20200702

In this thesis, we focus on computing the rank of divisors on two complete graphs appended at a common vertex. We come up with a formula that computes this rank in term of the rank of divisors on complete graph components. Although the formula is in an optimization form, it is good enough for us to compute this rank in polynomial time. Moreover, it is then used to study the length for the rank as well as the lengths of the first and the last plateaux of the rank function of divisors with the same reduced divisor and the number of chips at the sink as a variable.

In this thesis, we focus on computing the rank of divisors on two complete graphs appended at a common vertex. We come up with a formula that computes this rank in term of the rank of divisors on complete graph components. Although the formula is in an optimization form, it is good enough for us to compute this rank in polynomial time. Moreover, it is then used to study the length for the rank as well as the lengths of the first and the last plateaux of the rank function of divisors with the same reduced divisor and the number of chips at the sink as a variable.

In this thesis, we focus on computing the rank of divisors on two complete graphs appended at a common vertex. We come up with a formula that computes this rank in term of the rank of divisors on complete graph components. Although the formula is in an optimization form, it is good enough for us to compute this rank in polynomial time. Moreover, it is then used to study the length for the rank as well as the lengths of the first and the last plateaux of the rank function of divisors with the same reduced divisor and the number of chips at the sink as a variable.

PageRank was initially defined by S. Brin and L. Page for the purpose of measuring the importance of web pages (nodes) based on the structure of links between them. Due to existence of diverse methods of random walk on the graph, variants of PageRank now exists. They include traditional (or normal) PageRank due to normal random walk and Lazy PageRank due to lazy random walk on a graph. In this article, we establish how the two variants of PageRank changes when complete graphs are connected to a line of nodes whose links between the nodes are in one direction. Explicit formulae for the two variants of PageRank are presented. We have noted that the ranks on a line graph are the same except their numerical values which differ. Further, we have observed that both normal random walk and lazy random walk on complete graphs spend almost the same time at each node.

In this work, a set of sufficient conditions that guarantee consensus towards a pre-specified target state in double-integrator leader-follower proximity-based networks are derived. Since only the leader agents are aware of the global objective and proximity-based communication between agents is considered, the follower agents must not lose contact to the leaders. We establish a connectivity analysis framework which is used to show that the initial network topology is maintained if the ratio of leaders-to-followers and the magnitude of the goal attraction force experienced by the leaders are below certain bounds. Various network topologies are examined, starting from a complete graph and extending to incomplete graphs. The theoretical results are illustrated by simulations., QC 20161102

We introduce two operators on stable configurations of the sandpile model that provide an algorithmic bijection between recurrent and parking configurations. This bijection preserves their equivalence classes with respect to the sandpile group. The study of these operators in the special case of the complete bipartite graph Km,n naturally leads to a generalization of the well-known Cyclic Lemma of Dvoretsky and Motzkin, via pairs of periodic bi-infinite paths in the plane having slightly different slopes. We achieve our results by interpreting the action of these operators as an action on a point in the grid ℤ2 which is pointed to by one of these pairs of paths. Our Cyclic Lemma allows us to enumerate several classes of polyominoes, and therefore builds on the work of Irving and Rattan (2009), Chapman et al. (2009), and Bonin et al. (2003)., SCOPUS: ar.j, info:eu-repo/semantics/published

Orienteering problem (OP) is an NP-Hard graph problem. The nodes of the graph are associated with scores or rewards and the edges with time delays. The goal is to obtain a Hamiltonian path connecting the two necessary check points, i.e. the source and the target along with a set of control points such that the total collected score is maximized within a specified time limit. OP finds application in several fields like logistics, transportation networks, tourism industry, etc. Most of the existing algorithms for OP can only be applied on complete graphs that satisfy the triangle inequality. Real-life scenario does not guarantee that there exists a direct link between all control point pairs or the triangle inequality is satisfied. To provide a more practical solution, we propose a stochastic greedy algorithm (RWS_OP) that uses the roulette wheel selectionmethod, does not require that the triangle inequality condition is satisfied and is capable of handling both complete as well as incomplete graphs. Based on several experiments on standard benchmark data we show that RWS_OP is faster, more efficient in terms of time budget utilization and achieves a better performance in terms of the total collected score ascompared to a recently reported algorithm for incomplete graphs.

We show that asymptotically almost surely a tree with m edges decomposes the complete bipartite graph K2m,2m, a result connected to a conjecture of Graham and Häggkvist. The result also implies that asymptotically almost surely a tree with m edges decomposes the complete graph with O(m2) edges. An ingredient of the proof consists in showing that the bipartition classes of the base tree of a random tree have roughly equal size. © Cambridge University Press 2013., Peer Reviewed, Postprint (author’s final draft)

For each graph G the dimension of G is defined as the smallest dimension in the Euclidean Space where there is an embedding in which all the edges of G are segments of a straight line of length one. The exact value is calculated for some important families of graphs and this value is compared with other invariants. An infinite quantity of forbidden graphs for dimension 2 is also shown

For each graph G the dimension of G is defined as the smallest dimension in the Euclidean Space where there is an embedding in which all the edges of G are segments of a straight line of length one. The exact value is calculated for some important families of graphs and this value is compared with other invariants. An infinite quantity of forbidden graphs for dimension 2 is also shown

For each graph G the dimension of G is defined as the smallest dimension in the Euclidean Space where there is an embedding in which all the edges of G are segments of a straight line of length one. The exact value is calculated for some important families of graphs and this value is compared with other invariants. An infinite quantity of forbidden graphs for dimension 2 is also shown

For each graph G the dimension of G is defined as the smallest dimension in the Euclidean Space where there is an embedding in which all the edges of G are segments of a straight line of length one. The exact value is calculated for some important families of graphs and this value is compared with other invariants. An infinite quantity of forbidden graphs for dimension 2 is also shown

For each graph G the dimension of G is defined as the smallest dimension in the Euclidean Space where there is an embedding in which all the edges of G are segments of a straight line of length one. The exact value is calculated for some important families of graphs and this value is compared with other invariants. An infinite quantity of forbidden graphs for dimension 2 is also shown

[Formulae and special characters can only be approximated here. Please see the pdf version of the abstract for an accurate reproduction.] This thesis concerns the study of homogeneous factorisations of complete graphs with edge-transitive factors. A factorisation of a complete graph Kn is a partition of its edges into disjoint classes. Each class of edges in a factorisation of Kn corresponds to a spanning subgraph called a factor. If all the factors are isomorphic to one another, then a factorisation of Kn is called an isomorphic factorisation. A homogeneous factorisation of a complete graph is an isomorphic factorisation where there exists a group G which permutes the factors transitively, and a normal subgroup M of G such that each factor is M-vertex-transitive. If M also acts edge-transitively on each factor, then a homogeneous factorisation of Kn is called an edge-transitive homogeneous factorisation. The aim of this thesis is to study edge-transitive homogeneous factorisations of Kn. We achieve a nearly complete explicit classification except for the case where G is an affine 2-homogeneous group of the form ZR p x G0, where G0 is less than or equal to ΓL(1,p to the power of R). In this case, we obtain necessary and sufficient arithmetic conditions on certain parameters for such factorisations to exist, and give a generic construction that specifies the homogeneous factorisation completely, given that the conditions on the parameters hold. Moreover, we give two constructions of infinite families of examples where we specify the parameters explicitly. In the second infinite family, the arc-transitive factors are generalisations of certain arc-transitive, self-complementary graphs constructed by Peisert in 2001., Thesis (Ph.D.)--University of Western Australia, 2004

A general and simple method for constructing triangular and L2 type partially balanced incomplete block (PBIB) designs is presented. This method unifies several well-known methods and produces many new series of designs. The idea is based on a well-known relation between triangular and L2 type PBIB designs and line graphs. Triangular or L2 type PBIB designs can often be obtained by suitably symmetrizing a given initial block. (Author), Sponsored in part by Grants AFOSR-80-0170, AFOSR-76-3050 and NSF-MCS81-01727.