Search results for "Graph theory"
showing 10 items of 784 documents
Automorphisms and abstract commensurators of 2-dimensional Artin groups
2004
In this paper we consider the class of 2-dimensional Artin groups with connected, large type, triangle-free defining graphs (type CLTTF). We classify these groups up to isomorphism, and describe a generating set for the automorphism group of each such Artin group. In the case where the defining graph has no separating edge or vertex we show that the Artin group is not abstractly commensurable to any other CLTTF Artin group. If, moreover, the defining graph satisfies a further `vertex rigidity' condition, then the abstract commensurator group of the Artin group is isomorphic to its automorphism group and generated by inner automorphisms, graph automorphisms (induced from automorphisms of the…
Chromatic sums for colorings avoiding monochromatic subgraphs
2015
Abstract Given graphs G and H, a vertex coloring c : V ( G ) → N is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ ( H , G ) , is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G , Σ ( H , G ) , is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for Σ ( H , G ) , discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, G k with the property that k more colors than χ ( …
Decremental 2- and 3-connectivity on planar graphs
1996
We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total ofO(n logn) time under any sequence of at mostO(n) deletions. This givesO(logn) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total ofO(n log2n) time. This givesO(log2n) amortized time per deletion. The space required by all our data structures isO(n). All our time bounds improve previous bounds.
A Modified Tabu Thresholding Approach for the Generalised Restricted Vertex Colouring Problem
1996
We present a modification of the Tabu Thresholding (TT) approach and apply it to the solution of the generalised restricted vertex colouring problem. Both the bounded and unbounded cases are treated. In our algorithms, the basic TT elements are supplemented with an evaluation function that depends on the best solution obtained so far, together with a mechanism which reinforces the aggressive search in the improving phase, and new diversification strategies which depend on the state of the search. The procedure is illustrated through the solution of the problem of minimising the number of workers in a heterogeneous workforce.
A graph colouring model for assigning a heterogeneous workforce to a given schedule
1996
Abstract We analyze a heterogeneous workforce assignment problem in which the minimum number of workers required to carry out a machine load plan is calculated. The problem is formulated as a restricted vertex colouring problem and a branch and bound algorithm is presented. The special characteristics of the graph to be coloured allow an efficient implementation of the branch and bound. Computational results show that the algorithm can solve problems of 50 activities, 5, 10 and 15 machines and between 2 to 15 different types of workers in just a few seconds.
QSPR with descriptors based on averages of vertex invariants. An artificial neural network study
2014
New type of indices, the mean molecular connectivity indices (MMCI), based on nine different concepts of mean are proposed to model, together with molecular connectivity indices (MCI), experimental parameters and random variables, eleven properties of organic solvents. Two model methodologies are used to test the different descriptors: the multilinear least-squares (MLS) methodology and the Artificial Neural Network (ANN) methodology. The top three quantitative structure–property relationships (QSPR) for each property are chosen with the MLS method. The indices of these three QSPRs were used to train the ANNs that selected the best training sets of indices to estimate the evaluation sets of…
DEPFET Active Pixel Detectors for a Future Linear e(+)e(-) Collider
2013
arXiv:1212.2160v1.-- et al.
Systematic classification of two-loop realizations of the Weinberg operator
2015
We systematically analyze the $d=5$ Weinberg operator at 2-loop order. Using a diagrammatic approach, we identify two different interesting categories of neutrino mass models: (i) Genuine 2-loop models for which both, tree-level and 1-loop contributions, are guaranteed to be absent. And (ii) finite 2-loop diagrams, which correspond to the 1-loop generation of some particular vertex appearing in a given 1-loop neutrino mass model, thus being effectively 2-loop. From the large list of all possible 2-loop diagrams, the vast majority are infinite corrections to lower order neutrino mass models and only a moderately small number of diagrams fall into these two interesting classes. Moreover, all …
Non-Abelian Ball-Chiu vertex for arbitrary Euclidean momenta
2017
We determine the non-Abelian version of the four longitudinal form factors of the quark-gluon vertex, using exact expressions derived from the Slavnov-Taylor identity that this vertex satisfies. In addition to the quark and ghost propagators, a key ingredient of the present approach is the quark-ghost scattering kernel, which is computed within the one-loop dressed approximation. The vertex form factors obtained from this procedure are evaluated for arbitrary Euclidean momenta, and display features not captured by the well-known Ball-Chiu vertex, deduced from the Abelian (ghost-free) Ward identity. The potential phenomenological impact of these results is evaluated through the study of spec…
A gauge-technique Ansatz for the three gluon vertex of the background field method
2011
The vertex connecting one background gluon with two quantum ones constitutes a central ingredient in the gauge-invariant Schwinger-Dyson equation that determines the non-perturbative dynamics of the gluon propagator. This vertex satisfies a Ward identity with respect to the background gluon, and a Slavnov-Taylor identity with respect to the two quantum gluons. We present a complete Ansatz for this vertex, which satisfies both aforementioned identities. This entire construction depends crucially on a set of constraints relating the various form-factors of the ghost Green's functions appearing in the Slavnov-Taylor identity satisfied by the vertex. The validity of these constraints is demonst…