Página 1 dos resultados de 19 itens digitais encontrados em 0.001 segundos

## The construction of the poset of regular execeptional graphs using equitable partitions

Fonte: Instituto Politécnico de Bragança
Publicador: Instituto Politécnico de Bragança

Tipo: Conferência ou Objeto de Conferência

ENG

Relevância na Pesquisa

56.66%

An exceptional graph is a connected graph with least eigenvalue greater than or equal to -2 which is not a generalized line graph.
It is shown that the set of regular exceptional graphs is partitioned in three layers. A (k,t)-regular set is a subset of the vertices of a graph, inducing a k-regular subgraph such that every vertex not in the subset has t neighbors in it. A new recursive construction of regular exceptional graphs is proposed, where each regular exceptional graph of the first and the second layer is constructed by a (0,2)-regular set extension.
In this talk we present an algorithm based on this recursive construction and show that this technique induces a partial order relation on the set of regular exceptional graphs. The process of extending a graph is reduced to the construction of the incidence matrix of a combinatorial 1-design, considering several rules to prevent the production of isomorphic graphs, and we show that each regular exceptional graph has an equitable partition which, by this construction technique, is extended with a new element, the set of the additional vertices. The recursive construction is generalized to the construction of arbitrary families of regular graphs, by extending a regular graph G with another regular graph H such that V(H) is a (k...

Link permanente para citações:

## Spectral results on graphs with regularity constraints

Fonte: Elsevier
Publicador: Elsevier

Tipo: Artigo de Revista Científica

ENG

Relevância na Pesquisa

46.78%

#Equitable partitions#Graph spectra#Graph theory#Strongly regular graphs#Constrained optimization#Eigenvalues and eigenfunctions#Matrix algebra

Graphs with (k, τ)-regular sets and equitable partitions are examples of graphs with regularity constraints. A (k, τ)-regular set of a graph G is a subset of vertices S ⊆ V(G) inducing a k-regular subgraph and such that each vertex not in S has τ neighbors in S. The existence of such structures in a graph provides some information about the eigenvalues and eigenvectors of its adjacency matrix. For example, if a graph G has a (k1, τ1)-regular set S1 and a (k2, τ2)-regular set S2 such that k1 - τ1 = k2 - τ2 = λ, then λ is an eigenvalue of G with a certain eigenvector. Additionally, considering primitive strongly regular graphs, a necessary and sufficient condition for a particular subset of vertices to be (k, τ)-regular is introduced. Another example comes from the existence of an equitable partition in a graph. If a graph G, has an equitable partition π then its line graph, L(G), also has an equitable partition, over(π, ̄), induced by π, and the adjacency matrix of the quotient graph L (G) / over(π, ̄) is obtained from the adjacency matrix of G/π. © 2006 Elsevier Inc. All rights reserved.; CEOC; FCT; FEDER

Link permanente para citações:

## Laplacian eigenvectors and eigenvalues and almost equitable partitions

Fonte: Elsevier
Publicador: Elsevier

Tipo: Artigo de Revista Científica

ENG

Relevância na Pesquisa

46.77%

Relations between Laplacian eigenvectors and eigenvalues and the existence of almost equitable partitions (which are generalizations of equitable partitions) are presented. Furthermore, on the basis of some properties of the adjacency eigenvectors of a graph, a necessary and sufficient condition for the graph to be primitive strongly regular is introduced. © 2006 Elsevier Ltd. All rights reserved.; CEOC; FCT; FEDER

Link permanente para citações:

## Equitable bipartitions of graphs and related results

Fonte: Springer Verlag
Publicador: Springer Verlag

Tipo: Artigo de Revista Científica

ENG

Relevância na Pesquisa

36.34%

CEOC; FCT; FEDER

Link permanente para citações:

## On the eigenvalues of Euclidean distance matrices

Fonte: Sociedade Brasileira de Matemática Aplicada e Computacional
Publicador: Sociedade Brasileira de Matemática Aplicada e Computacional

Tipo: Artigo de Revista Científica
Formato: text/html

Publicado em 01/01/2008
EN

Relevância na Pesquisa

46.55%

In this paper, the notion of equitable partitions (EP) is used to study the eigenvalues of Euclidean distance matrices (EDMs). In particular, EP is used to obtain the characteristic polynomials of regular EDMs and non-spherical centrally symmetric EDMs. The paper also presents methods for constructing cospectral EDMs and EDMs with exactly three distinct eigenvalues.

Link permanente para citações:

## Solving hard instances of maximum stable set problem by equitable partitions

Fonte: La Sapienza Universidade de Roma
Publicador: La Sapienza Universidade de Roma

Tipo: Tese de Doutorado

EN_US

Relevância na Pesquisa

46.55%

#Integer Programming#Maximum Stable Set Problem#Symmetry#Equitable Partitions#1zc graphs#Settori Disciplinari MIUR::Scienze matematiche e informatiche::RICERCA OPERATIVA

Link permanente para citações:

## Block transitivity and degree matrices

Fonte: ACADEMIC PRESS
Publicador: ACADEMIC PRESS

Tipo: Artículo de revista

EN

Relevância na Pesquisa

36.34%

We say that a square matrix M of order r is a degree matrix of a given graph G if there is a so-called equitable partition of its vertices into r blocks with the following property: For any i and j it holds that a vertex from the ith block of the partition has exactly m(i,j) neighbors inside the jth block.
We ask whether for a given degree matrix M, there exists a graph G such that M is a degree matrix of G, and in addition, for any two edges e, f spanning between the same pair of blocks there exists an automorphism of G that sends e to f. In this work we affirmatively answer the question for all degree matrices and show a way to construct a graph that witnesses this fact.
We further explore a case where the automorphism is required to exchange a given pair of edges and show some positive and negative results.

Link permanente para citações:

## Scalable Positional Analysis for Studying Evolution of Nodes in Networks

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

26.34%

In social network analysis, the fundamental idea behind the notion of
position is to discover actors who have similar structural signatures.
Positional analysis of social networks involves partitioning the actors into
disjoint sets using a notion of equivalence which captures the structure of
relationships among actors. Classical approaches to Positional Analysis, such
as Regular equivalence and Equitable Partitions, are too strict in grouping
actors and often lead to trivial partitioning of actors in real world networks.
An Epsilon Equitable Partition (EEP) of a graph, which is similar in spirit to
Stochastic Blockmodels, is a useful relaxation to the notion of structural
equivalence which results in meaningful partitioning of actors. In this paper
we propose and implement a new scalable distributed algorithm based on
MapReduce methodology to find EEP of a graph. Empirical studies on random
power-law graphs show that our algorithm is highly scalable for sparse graphs,
thereby giving us the ability to study positional analysis on very large scale
networks. We also present the results of our algorithm on time evolving
snapshots of the facebook and flickr social graphs. Results show the importance
of positional analysis on large dynamic networks.; Comment: Presented at the workshop on Mining Networks and Graphs: A Big Data
Analytic Challenge...

Link permanente para citações:

## On the Godsil -- Higman necessary condition for equitable partitions of association schemes

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 18/06/2013

Relevância na Pesquisa

46.77%

In the monograph 'Association schemes', C. Godsil derived a necessary
condition for equitable partitions of association schemes and noticed that it
could be used to show that certain equitable partitions do not exist. In this
short note, we show that, in fact, this condition is not stronger than the
well-known Lloyd theorem.

Link permanente para citações:

## Equitable Partitioning Policies for Mobile Robotic Networks

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 30/03/2009

Relevância na Pesquisa

36.53%

The most widely applied strategy for workload sharing is to equalize the
workload assigned to each resource. In mobile multi-agent systems, this
principle directly leads to equitable partitioning policies in which (i) the
workspace is divided into subregions of equal measure, (ii) there is a
bijective correspondence between agents and subregions, and (iii) each agent is
responsible for service requests originating within its own subregion. In this
paper, we design provably correct, spatially-distributed and adaptive policies
that allow a team of agents to achieve a convex and equitable partition of a
convex workspace, where each subregion has the same measure. We also consider
the issue of achieving convex and equitable partitions where subregions have
shapes similar to those of regular polygons. Our approach is related to the
classic Lloyd algorithm, and exploits the unique features of power diagrams. We
discuss possible applications to routing of vehicles in stochastic and dynamic
environments. Simulation results are presented and discussed.; Comment: Paper submitted to IEEE Transactions on Automatic Control in December
2008

Link permanente para citações:

## Perfect state transfer, graph products and equitable partitions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 07/09/2010

Relevância na Pesquisa

36.55%

We describe new constructions of graphs which exhibit perfect state transfer
on continuous-time quantum walks. Our constructions are based on variants of
the double cones [BCMS09,ANOPRT10,ANOPRT09] and the Cartesian graph products
(which includes the n-cube) [CDDEKL05]. Some of our results include: (1) If $G$
is a graph with perfect state transfer at time $t_{G}$, where $t_{G}\Spec(G)
\subseteq \ZZ\pi$, and $H$ is a circulant with odd eigenvalues, their weak
product $G \times H$ has perfect state transfer. Also, if $H$ is a regular
graph with perfect state transfer at time $t_{H}$ and $G$ is a graph where
$t_{H}|V_{H}|\Spec(G) \subseteq 2\ZZ\pi$, their lexicographic product $G[H]$
has perfect state transfer. (2) The double cone $\overline{K}_{2} + G$ on any
connected graph $G$, has perfect state transfer if the weights of the cone
edges are proportional to the Perron eigenvector of $G$. This generalizes
results for double cone on regular graphs studied in
[BCMS09,ANOPRT10,ANOPRT09]. (3) For an infinite family $\GG$ of regular graphs,
there is a circulant connection so the graph $K_{1}+\GG\circ\GG+K_{1}$ has
perfect state transfer. In contrast, no perfect state transfer exists if a
complete bipartite connection is used (even in the presence of weights)
[ANOPRT09]. We also describe a generalization of the path collapsing argument
[CCDFGS03...

Link permanente para citações:

## Epidemic Outbreaks in Networks with Equitable or Almost-Equitable Partitions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

36.53%

We study the diffusion of epidemics on networks that are partitioned into
local communities. The gross structure of hierarchical networks of this kind
can be described by a quotient graph. The rationale of this approach is that
individuals infect those belonging to the same community with higher
probability than individuals in other communities. In community models the
nodal infection probability is thus expected to depend mainly on the
interaction of a few, large interconnected clusters. In this work, we describe
the epidemic process as a continuous-time individual-based
susceptible-infected-susceptible (SIS) model using a first-order mean-field
approximation. A key feature of our model is that the spectral radius of this
smaller quotient graph (which only captures the macroscopic structure of the
community network) is all we need to know in order to decide whether the
overall healthy-state defines a globally asymptotically stable or an unstable
equilibrium. Indeed, the spectral radius is related to the epidemic threshold
of the system. Moreover we prove that, above the threshold, another
steady-state exists that can be computed using a lower-dimensional dynamical
system associated with the evolution of the process on the quotient graph. Our
investigations are based on the graph-theoretical notion of equitable partition
and of its recent and rather flexible generalization...

Link permanente para citações:

## Square Property, Equitable Partitions, and Product-like Graphs

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

46.55%

Equivalence relations on the edge set of a graph $G$ that satisfy restrictive
conditions on chordless squares play a crucial role in the theory of Cartesian
graph products and graph bundles. We show here that such relations in a natural
way induce equitable partitions on the vertex set of $G$, which in turn give
rise to quotient graphs that can have a rich product structure even if $G$
itself is prime.; Comment: 20 pages, 6 figures

Link permanente para citações:

## alpha-Kuramoto partitions: graph partitions from the frustrated Kuramoto model generalise equitable partitions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 18/06/2013

Relevância na Pesquisa

36.65%

#Mathematics - Combinatorics#Condensed Matter - Statistical Mechanics#Nonlinear Sciences - Chaotic Dynamics

The Kuramoto model describes the collective dynamics of a system of coupled
oscillators. An alpha-Kuramoto partition is a graph partition induced by the
Kuramoto model, when the oscillators include a phase frustration parameter. We
prove that every equitable partition is an alpha-Kuramoto partition, but that
the converse does necessarily not hold. We give an exact characterisation of
alpha-Kuramoto bipartitions.; Comment: 7 pages, 3 EPS figures

Link permanente para citações:

## Measuring dependence powerfully and equitably

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

16.34%

#Statistics - Methodology#Computer Science - Information Theory#Computer Science - Learning#Quantitative Biology - Quantitative Methods#Statistics - Machine Learning

For high-dimensional datasets, it is common to evaluate a measure of
dependence on every variable pair and retain the highest-scoring pairs for
follow-up. If the statistic used systematically assigns higher scores to some
relationship types over others, important relationships may be overlooked. This
difficulty is avoided if the statistic is equitable [Reshef et al. 2015a],
i.e., if, for some measure of noise, it assigns similar scores to equally noisy
relationships regardless of relationship type.
In this paper, we introduce and characterize a population measure of
dependence called MIC*. We show three ways that MIC* can be viewed: as the
population value of MIC, a highly equitable statistic from [Reshef et al.
2011], as a canonical "smoothing" of mutual information, and as the supremum of
an infinite sequence defined in terms of optimal one-dimensional partitions of
the marginals of the joint distribution. Based on this theory, we introduce an
efficient algorithm for computing MIC* from the density of a pair of random
variables, and we define a new consistent estimator MICe for MIC* that is
efficiently computable. (In contrast, there is no known polynomial-time
algorithm for computing MIC.) We show through simulations that MICe has better
bias-variance properties than MIC...

Link permanente para citações:

## Perfect colorings of $Z^2$: Nine colors

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 30/12/2008

Relevância na Pesquisa

26.12%

We list all perfect colorings of $Z^2$ by 9 or less colors. Keywords: perfect
colorings, equitable partitions; Comment: 177 pages (large Appendix). !Attention: .ps is 17Mb, .pdf is 1.6Mb,
archived source is 40kb

Link permanente para citações:

## Equitable Decompositions of Graphs

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 14/10/2015

Relevância na Pesquisa

36.46%

The automorphisms of a graph can be used to characterize the graph's
symmetries. Here we show that if a graph has any kind of symmetry, it is
possible to decompose the graph's (weighted) adjacency matrix $A$ into a number
of smaller matrices with respect to any one of its automorphisms. The
collective eigenvalues of these resulting matrices are the same as the
eigenvalues of the original matrix $A$. Because this decomposition has
connections to the theory of equitable partitions it is referred to as an
$\textit{equitable decomposition}$. This method of decomposition can also be
used on any other matrix that can be associated with a graph, so long as the
matrix respects the symmetries of the graph. This includes, for instance,
Laplacian matrices. Moreover, the techniques used to equitably decompose a
graph can be used to bound the number of simple eigenvalues of undirected
graphs.

Link permanente para citações:

## New infinite families of directed strongly regular graphs via equitable partitions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 01/04/2015

Relevância na Pesquisa

46.66%

In this paper we introduce a construction of directed strongly regular graphs
from smaller ones using equitable partitions. Each equitable partition of a
single DSRG satisfying several conditions leads to an infinite family of
directed strongly regular graphs. We construct in this way dozens of infinite
families. For order at most 110, we confirm the existence of DSRGs for 30
previously open parameter sets.; Comment: 27 pages

Link permanente para citações:

## Structure-preserving model reduction of physical network systems by clustering

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 19/03/2014

Relevância na Pesquisa

26.55%

In this paper, we establish a method for model order reduction of a certain
class of physical network systems. The proposed method is based on clustering
of the vertices of the underlying graph, and yields a reduced order model
within the same class. To capture the physical properties of the network, we
allow for weights associated to both the edges as well as the vertices of the
graph. We extend the notion of almost equitable partitions to this class of
graphs. Consequently, an explicit model reduction error expression in the sense
of H2-norm is provided for clustering arising from almost equitable partitions.
Finally the method is extended to second-order systems.

Link permanente para citações: