Large-scale networks have become ubiquitous elements of our society. Modern social networks, supported by communication and travel technology, have grown in size and complexity to unprecedented ...scales. Computer networks, such as the Internet, have a fundamental impact on commerce, politics and culture. The study of networks is also central in biology, chemistry and other natural sciences. Unifying aspects of these networks are a small maximum degree and a small diameter, which are also shared by many network models, such as small-world networks. Graph theoretical methodologies can be instrumental in the challenging task of predicting, constructing and studying the properties of large-scale networks. This task is now necessitated by the vulnerability of large networks to phenomena such as cross-continental spread of disease and botnets (networks of malware). In this article, we produce the new largest known networks of maximum degree 17 ≤ A ≤ 20 and diameter 2 ≤ D ≤ 10, using a wide range of techniques and concepts, such as graph compounding, vertex duplication, Kronecker product, polarity graphs and voltage graphs. In this way, we provide new benchmarks for networks with given maximum degree and diameter, and a complete overview of state-of-the-art methodology that can be used to construct such networks. PUBLICATION ABSTRACT
We consider graphs of maximum degree 3, diameter
D
≥
2
and at most 4 vertices less than the Moore bound
M
3
,
D
, that is,
(
3
,
D
,
−
ϵ
)
-graphs for
ϵ
≤
4
.
We prove the non-existence of
(
3
,
D
,
...−
4
)
-graphs for
D
≥
5
, completing in this way the catalogue of
(
3
,
D
,
−
ϵ
)
-graphs with
D
≥
2
and
ϵ
≤
4
. Our results also give an improvement to the upper bound on the largest possible number
N
3
,
D
of vertices in a graph of maximum degree 3 and diameter
D
, so that
N
3
,
D
≤
M
3
,
D
−
6
for
D
≥
5
.
New largest known graphs of diameter 6 Pineda-Villavicencio, Guillermo; Gómez, José; Miller, Mirka ...
Networks,
July 2009, Letnik:
53, Številka:
4
Journal Article
New Largest Graphs of Diameter 6 Pineda-Villavicencio, Guillermo; Gómez, José; Miller, Mirka ...
Electronic notes in discrete mathematics,
07/2006, Letnik:
24
Journal Article
Odprti dostop
In the pursuit of obtaining largest graphs of given degree and diameter, many construction techniques have arisen. Compounding of graphs is one such technique. In this paper, by means of the ...compounding of complete graphs into the bipartite Moore graph of diameter 6, we obtain two families of (Δ, 6)-graphs. For maximum degree Δ > 4, being Δ − 1 a prime power, the members of these families constitute the largest known graphs of diameter 6.
We quantify why, as designers, we should prefer clique-based hypercubes (K-cubes) over traditional hypercubes based on cycles (C-cubes). Reaping fresh analytic results, we find that K-cubes minimize ...the wirecount and, simultaneously, the latency of hypercube architectures that tolerate failure of any f nodes. Refining the graph model of Hayes (1976), we pose the feasibility of configuration as a problem in multivariate optimization: What (f+1)-connected n-vertex graphs with fewest edges n(f+1)/2 minimize the maximum a) radius or b) diameter of subgraphs (i.e., quorums) induced by deleting up to f vertices? We solve (1) for f that is superlogarithmic but sublinear in n and, in the process, prove: 1) the fault tolerance of K-cubes is proportionally greater than that of C-cubes; 2) quorums formed from K-cubes have a diameter that is asymptotically convergent to the Moore Bound on radius; 3) under any conditions of scaling, by contrast, C-cubes diverge from the Moore Bound. Thus, K-cubes are optimal, while C-cubes are suboptimal. Our exposition furthermore: 4) counterexamples, corrects, and generalizes a mistaken claim by Armstrong and Gray (1981) concerning binary cubes; 5) proves that K-cubes and certain of their quorums are the only graphs which can be labeled such that the edge distance between any two vertices equals the Hamming distance between their labels; and 6) extends our results to K-cube-connected cycles and edges. We illustrate and motivate our work with applications to the synthesis of multicomputer architectures for deep space missions.
Multicast network traffic is information with one source node, but many destination nodes. Rather than setting up individual connections between the source node and each destination node, or ...broadcasting the information to the entire network, multicasting efficiently exploits link capacity by allowing the source node to transmit a small number of copies of the information to mutually-exclusive groups of destination nodes. Multicasting is an important topic in the fields of networking (video and audio conferencing, video on demand, local-area network interconnection) and computer architecture (cache coherency, multiprocessor message passing). In this paper, we derive approximate expressions for the minimum cost (in terms of link utilization) of shortest-path multicast traffic in arbitrary tree networks. Our results provide a theoretical best-case scenario for link utilization of multicast distribution in tree topologies overlaid onto arbitrary graphs. In real networks such as the Internet MBONE, multicast distribution paths are often tree-like, but contain some cycles for purposes of fault tolerance. We find that even for richly-connected graphs such as the shufflenet and the hypercube, our expression provides a good prediction of the cost (in terms of link utilization) of multicast communication. Thus, this theoretical result has two applications: (1) a lower bound on the link capacity required for multicasting in random tree topologies, and (2) an approximation of the cost of multicasting in regular LAN and MAN topologies.
In this note we construct a new infinite family of (q - 1)-regular graphs of girth 8 and order 2q(q - 1)(2) for all prime powers q >= 16, which are the smallest known so far whenever q - 1 is not a ...prime power or a prime power plus one itself.
Peer Reviewed
PDF
