Your selections:

14Lin, Yuqing
13Baca, Martin
13Sugeng, Kiki Ariyanti
9Ryan, Joe
6Balbuena, Camino
5Baskoro, Edy
5Slamin,
4Nguyen, Minh Hoang
4Pineda-Villavicencio, Guillermo
3Cholily, Yus Mochamad
3Gimbert, Joan
3Simanjuntak, Rinovia
2Barker, Ewan
2Jendrol, Stanislav
2Marcote, Xavier
2Siran, Jozef
2Tang, Jianmin
2Tuga, Mauritsius
1Dafik

Show More

Show Less

11Graph theory
8Antimagic labeling
5Moore bound
40802 Computation Theory and Mathematics
4Connectivity
4Degree/diameter problem
4Number theory
4Theorem proving
3Graph labeling
3Numerical methods
3Problem solving
3Sum graph
2(k,g)-cage
20103 Numerical and Computational Mathematics
2Almost Moore digraph
2Diameter
2Digraphs
2Genetic algorithms
2Integer programming

Show More

Show Less

Format Type

On large bipartite graphs of diameter 3

- Feria-Purón, Ramiro, Miller, Mirka, Pineda-Villavicencio, Guillermo

**Authors:**Feria-Purón, Ramiro , Miller, Mirka , Pineda-Villavicencio, Guillermo**Date:**2013**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 313, no. 4 (2013), p. 381-390**Relation:**http://purl.org/au-research/grants/arc/DP110102011**Full Text:****Reviewed:****Description:**We consider the bipartite version of the degree/diameter problem, namely, given natural numbers dâ‰¥2 and Dâ‰¥2, find the maximum number N b(d,D) of vertices in a bipartite graph of maximum degree d and diameter D. In this context, the bipartite Moore bound Mb(d,D) represents a general upper bound for Nb(d,D). Bipartite graphs of order Mb(d,D) are very rare, and determining Nb(d,D) still remains an open problem for most (d,D) pairs. This paper is a follow-up of our earlier paper (Feria-PurÃ³n and Pineda-Villavicencio, 2012 [5]), where a study on bipartite (d,D,-4)-graphs (that is, bipartite graphs of order M b(d,D)-4) was carried out. Here we first present some structural properties of bipartite (d,3,-4)-graphs, and later prove that there are no bipartite (7,3,-4)-graphs. This result implies that the known bipartite (7,3,-6)-graph is optimal, and therefore Nb(7,3)=80. We dub this graph the Hafner-Loz graph after its first discoverers Paul Hafner and Eyal Loz. The approach here presented also provides a proof of the uniqueness of the known bipartite (5,3,-4)-graph, and the non-existence of bipartite (6,3,-4)-graphs. In addition, we discover at least one new largest known bipartite-and also vertex-transitive-graph of degree 11, diameter 3 and order 190, a result which improves by four vertices the previous lower bound for Nb(11,3). © 2012 Elsevier B.V. All rights reserved.**Description:**2003011037

**Authors:**Feria-Purón, Ramiro , Miller, Mirka , Pineda-Villavicencio, Guillermo**Date:**2013**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 313, no. 4 (2013), p. 381-390**Relation:**http://purl.org/au-research/grants/arc/DP110102011**Full Text:****Reviewed:****Description:**We consider the bipartite version of the degree/diameter problem, namely, given natural numbers dâ‰¥2 and Dâ‰¥2, find the maximum number N b(d,D) of vertices in a bipartite graph of maximum degree d and diameter D. In this context, the bipartite Moore bound Mb(d,D) represents a general upper bound for Nb(d,D). Bipartite graphs of order Mb(d,D) are very rare, and determining Nb(d,D) still remains an open problem for most (d,D) pairs. This paper is a follow-up of our earlier paper (Feria-PurÃ³n and Pineda-Villavicencio, 2012 [5]), where a study on bipartite (d,D,-4)-graphs (that is, bipartite graphs of order M b(d,D)-4) was carried out. Here we first present some structural properties of bipartite (d,3,-4)-graphs, and later prove that there are no bipartite (7,3,-4)-graphs. This result implies that the known bipartite (7,3,-6)-graph is optimal, and therefore Nb(7,3)=80. We dub this graph the Hafner-Loz graph after its first discoverers Paul Hafner and Eyal Loz. The approach here presented also provides a proof of the uniqueness of the known bipartite (5,3,-4)-graph, and the non-existence of bipartite (6,3,-4)-graphs. In addition, we discover at least one new largest known bipartite-and also vertex-transitive-graph of degree 11, diameter 3 and order 190, a result which improves by four vertices the previous lower bound for Nb(11,3). © 2012 Elsevier B.V. All rights reserved.**Description:**2003011037

On the nonexistence of graphs of diameter 2 and defect 2

- Miller, Mirka, Nguyen, Minh Hoang, Pineda-Villavicencio, Guillermo

**Authors:**Miller, Mirka , Nguyen, Minh Hoang , Pineda-Villavicencio, Guillermo**Date:**2009**Type:**Text , Journal article**Relation:**The Journal of Combinatorial Mathematics and Combinatorial Computing Vol. 71, no. (2009), p. 5-20**Full Text:**false**Reviewed:****Description:**In 1960, Hoffman and Singleton investigated the existence of Moore graphs of diameter 2 (graphs of maximum degree d and d² + 1 vertices), and found that such graphs exist only for d = 2; 3; 7 and possibly 57. In 1980, Erdös et al., using eigenvalue analysis, showed that, with the exception of C4, there are no graphs of diameter 2, maximum degree d and d² vertices. In this paper, we show that graphs of diameter 2, maximum degree d and d² - 1 vertices do not exist for most values of d with d ≥ 6, and conjecture that they do not exist for any d ≥ 6.**Description:**2003007893

Enumerations of vertex orders of almost Moore digraphs with selfrepeats

- Baskoro, Edy, Cholily, Yus Mochamad, Miller, Mirka

**Authors:**Baskoro, Edy , Cholily, Yus Mochamad , Miller, Mirka**Date:**2008**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 308, no. 1 (2008), p. 123-128**Full Text:**false**Reviewed:****Description:**An almost Moore digraph G of degree d > 1, diameter k > 1 is a diregular digraph with the number of vertices one less than the Moore bound. If G is an almost Moore digraph, then for each vertex u ∈ V (G) there exists a vertex v ∈ V (G), called repeat of u and denoted by r (u) = v, such that there are two walks of length ≤ k from u to v. The smallest positive integer p such that the composition rp (u) = u is called the order of u. If the order of u is 1 then u is called a selfrepeat. It is known that if G is an almost Moore digraph of diameter k ≥ 3 then G contains exactly k selfrepeats or none. In this paper, we propose an exact formula for the number of all vertex orders in an almost Moore digraph G containing selfrepeats, based on the vertex orders of the out-neighbours of any selfrepeat vertex. © 2007 Elsevier B.V. All rights reserved.**Description:**C1

Graphs of order two less than the Moore bound

- Miller, Mirka, Simanjuntak, Rinovia

**Authors:**Miller, Mirka , Simanjuntak, Rinovia**Date:**2008**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 308, no. 13 (2008), p. 2810-2821**Full Text:**false**Reviewed:****Description:**The Moore bound for a directed graph of maximum out-degree d and diameter k is Md,k=1+d+d2++dk. It is known that digraphs of order Md,k (Moore digraphs) do not exist for d>1 and k>1. Similarly, the Moore bound for an undirected graph of maximum degree d and diameter k is . Undirected Moore graphs only exist in a small number of cases. Mixed (or partially directed) Moore graphs generalize both undirected and directed Moore graphs. In this paper, we shall show that all known mixed Moore graphs of diameter k=2 are unique and that mixed Moore graphs of diameter k3 do not exist.**Description:**C1

HSAGA and its application for the construction of near-Moore digraphs

- Tang, Jianmin, Miller, Mirka, Lin, Yuqing

**Authors:**Tang, Jianmin , Miller, Mirka , Lin, Yuqing**Date:**2008**Type:**Text , Journal article**Relation:**Journal of Discrete Algorithms Vol. 6, no. 1 (2008), p. 73-84**Full Text:**false**Reviewed:****Description:**The degree/diameter problem is to determine the largest graphs or digraphs of given maximum degree and given diameter. This paper deals with directed graphs. General upper bounds, called Moore bounds, exist for the largest possible order of such digraphs of maximum degree d and given diameter k. It is known that simulated annealing and genetic algorithm are effective techniques to identify global optimal solutions. This paper describes our attempt to build a Hybrid Simulated Annealing and Genetic Algorithm (HSAGA) that can be used to construct large digraphs. We present our new results obtained by HSAGA, as well as several related open problems. © 2007 Elsevier B.V. All rights reserved.**Description:**C1

Moore bound for mixed networks

- Nguyen, Minh Hoang, Miller, Mirka

**Authors:**Nguyen, Minh Hoang , Miller, Mirka**Date:**2008**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 308, no. 23 (Dec 2008), p. 5499-5503**Full Text:**false**Reviewed:****Description:**Mixed graphs contain both undirected as well as directed links between vertices and therefore are an interesting model for interconnection communication networks. In this paper, we establish the Moore bound for mixed graphs, which generalizes both the directed and the undirected Moore bound. Crown Copyright (C) 2007 Published by Elsevier B.V. All rights reserved.

New constructions of A-magic graphs using labeling matrices

- Sugeng, Kiki Ariyanti, Miller, Mirka

**Authors:**Sugeng, Kiki Ariyanti , Miller, Mirka**Date:**2008**Type:**Text , Journal article**Relation:**Journal of combinatorial mathematics and combinatorial computing Vol. 65, no. (May 2008), p. 147-151**Full Text:**false**Reviewed:**

On antimagic labelings of disjoint union of complete s-partite graphs

- Dafik, Miller, Mirka, Ryan, Joe, Baca, Martin

**Authors:**Dafik , Miller, Mirka , Ryan, Joe , Baca, Martin**Date:**2008**Type:**Text , Journal article**Relation:**Journal of combinatorial mathematics and combinatorial computing Vol. 65, no. (May 2008 2008), p. 41-49**Full Text:****Reviewed:****Description:**By an (a, d)-edge-antimagic total labeling of a graph G(V, E) we mean a bijective function f from V(G) u E(G) onto the set. { 1, 2, ... ,ǀV(C)ǀ+IE(G)I} such that the set of all the edge-weights, w(uv) ,.... f(u) + f(uv) + f(v), uv C E (G), is {a, a+ d, a+ 2d, . . . , a + (lE(G)I-1)d}, for two integers a > 0 and d

**Authors:**Dafik , Miller, Mirka , Ryan, Joe , Baca, Martin**Date:**2008**Type:**Text , Journal article**Relation:**Journal of combinatorial mathematics and combinatorial computing Vol. 65, no. (May 2008 2008), p. 41-49**Full Text:****Reviewed:****Description:**By an (a, d)-edge-antimagic total labeling of a graph G(V, E) we mean a bijective function f from V(G) u E(G) onto the set. { 1, 2, ... ,ǀV(C)ǀ+IE(G)I} such that the set of all the edge-weights, w(uv) ,.... f(u) + f(uv) + f(v), uv C E (G), is {a, a+ d, a+ 2d, . . . , a + (lE(G)I-1)d}, for two integers a > 0 and d

On graphs of maximum degree 3 and defect 4

- Pineda-Villavicencio, Guillermo, Miller, Mirka

**Authors:**Pineda-Villavicencio, Guillermo , Miller, Mirka**Date:**2008**Type:**Text , Journal article**Relation:**Journal of combinatorial mathematics and combinatorial computing Vol. 65, no. (May 2008), p. 25-31**Full Text:**false**Reviewed:****Description:**It is well known that apart from the Petersen graph there are no Moore graphs of degree 3. As a cubic graph must have an even number of vertices, there are no graphs of maximum degree 3 and

On the connectivity of (k, g)-cages of even girth

- Lin, Yuqing, Balbuena, Camino, Marcote, Xavier, Miller, Mirka

**Authors:**Lin, Yuqing , Balbuena, Camino , Marcote, Xavier , Miller, Mirka**Date:**2008**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 308, no. 15 (2008), p. 3249-3256**Full Text:**false**Reviewed:****Description:**A (k,g)-cage is a k-regular graph with girth g and with the least possible number of vertices. In this paper we give a brief overview of the current results on the connectivity of (k,g)-cages and we improve the current known best lower bound on the vertex connectivity of (k,g)-cages for g even. © 2007 Elsevier B.V. All rights reserved.**Description:**C1

Structural properties of graphs of diameter 2 with maximal repeats

- Nguyen, Minh Hoang, Miller, Mirka

**Authors:**Nguyen, Minh Hoang , Miller, Mirka**Date:**2008**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 308, no. 11 (Jun 2008), p. 2337-2341**Full Text:**false**Reviewed:****Description:**It was shown using eigenvalue analysis by Erdos et al. that with the exception of C-4, there are no graphs of diameter 2, of maximum degree d and of order d(2), that is, one less than the Moore bound. These graphs belong to a class of regular graphs of diameter 2, and having certain interesting structural properties, which will be proved in this paper. (c) 2007 Elsevier B.V. All rights reserved.**Description:**C1

Super antimagic total labeling of graphs

- Sugeng, Kiki Ariyanti, Miller, Mirka, Baca, Martin

**Authors:**Sugeng, Kiki Ariyanti , Miller, Mirka , Baca, Martin**Date:**2008**Type:**Text , Journal article**Relation:**Utilitas Mathematica Vol. 76, no. (2008), p. 161-171**Full Text:**false**Reviewed:****Description:**Let G = (V, E) be a simple, finite and undirected graph with v vertices and e edges, A graph labeling is a mapping from elements of a graph to a set of numbers (usually positive integers). If the domain of the mapping is the set of vertices (or edges) then the labeling is called vertex-labeling (or edge-labeling). If the domain of the mapping is the set of vertices and edges then the labeling is called total labeling. The sum of all labels associated with a graph element is called the weight of the element. If the weights of vertices (or the weights of edges) form an arithmetic progression starting at a and with difference d, then the labeling is called (a, d)-vertex-antimagic (or (a, d)-edge-antimagic). Such a labeling is called v-super (or e-super) if the smallest labels appear on the vertices (or edges). In this paper we present new results for v-super vertex-antimagic total and e-super edge-antimagic total labeling.**Description:**C1

A lower bound on the order of regular graphs with given girth pair

- Balbuena, Camino, Jiang, T., Lin, Yuqing, Marcote, Xavier, Miller, Mirka

**Authors:**Balbuena, Camino , Jiang, T. , Lin, Yuqing , Marcote, Xavier , Miller, Mirka**Date:**2007**Type:**Text , Journal article**Relation:**Journal of Graph Theory Vol. 55, no. 2 (2007), p. 153-163**Full Text:**false**Reviewed:****Description:**The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair was proved by Harary and Kovács [Regular graphs with given girth pair, J Graph Theory 7 (1983), 209-218]. A (**Description:**C1**Description:**2003004727

- Baca, Martin, Lin, Yuqing, Miller, Mirka

**Authors:**Baca, Martin , Lin, Yuqing , Miller, Mirka**Date:**2007**Type:**Text , Journal article**Relation:**Utilitas Mathematica Vol. 72, no. (2007), p. 65-75**Full Text:**false**Reviewed:****Description:**In this paper we deal with the problem of labeling the vertices, edges and faces of a grid graph by the consecutive integers from 1 to |V| + |E| + |F| in such a way that the label of a face and the labels of the vertices and edges surrounding that face all together add up to a weight of that face. These face weights then form an arithmetic progression with common difference d.**Description:**C1**Description:**2003004808

Diameter-sufficient conditions for a graph to be super-restricted connected

- Balbuena, Camino, Lin, Yuqing, Miller, Mirka

**Authors:**Balbuena, Camino , Lin, Yuqing , Miller, Mirka**Date:**2007**Type:**Text , Journal article**Relation:**Discrete Applied Mathematics Vol. , no. (2007), p.**Full Text:**false**Reviewed:****Description:**A vertex-cut X is said to be a restricted cut of a graph G if it is a vertex-cut such that no vertex u in G has all its neighbors in X. Clearly, each connected component of G - X must have at least two vertices. The restricted connectivity**Description:**C1

- Baca, Martin, Lin, Yuqing, Miller, Mirka, Youssef, Maged

**Authors:**Baca, Martin , Lin, Yuqing , Miller, Mirka , Youssef, Maged**Date:**2007**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 307, no. 11-12 (May 2007), p. 1232-1244**Full Text:**false**Reviewed:****Description:**For a graph G = (V, E), a bijection g from V(G) boolean OR E(G) into {1, 2,..., vertical bar V(G)vertical bar + vertical bar E(G)vertical bar} is called (a, d)-edge-antimagic total labeling of G if the edge-weights w(xy) = g(x) + g(y) + g(xy), xy E E(G), form an arithmetic progression starting from a and having common difference d. An (a, d)-edge-antimagic total labeling is called super (a, d)-edge-antimagic total if g(V(G)) = {1, 2,..., vertical bar V(G)vertical bar}. We study super (a, d)-edge-antimagic properties of certain classes of graphs, including friendship graphs, wheels, fans, complete graphs and complete bipartite graphs. (c) 2006 Elsevier B.V. All rights reserved.**Description:**2003004910

On irregular total labellings

- Baca, Martin, Jendrol, Stanislav, Miller, Mirka, Ryan, Joe

**Authors:**Baca, Martin , Jendrol, Stanislav , Miller, Mirka , Ryan, Joe**Date:**2007**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 307, no. 11-12 (May 2007), p. 1378-1388**Full Text:****Reviewed:****Description:**Two new graph characteristics, the total vertex irregularity strength and the total edge irregularity strength, are introduced. Estimations on these parameters are obtained. For some families of graphs the precise values of these parameters are proved. (c) 2006 Elsevier B.V. All rights reserved.**Description:**C1**Description:**2003004909

**Authors:**Baca, Martin , Jendrol, Stanislav , Miller, Mirka , Ryan, Joe**Date:**2007**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 307, no. 11-12 (May 2007), p. 1378-1388**Full Text:****Reviewed:****Description:**Two new graph characteristics, the total vertex irregularity strength and the total edge irregularity strength, are introduced. Estimations on these parameters are obtained. For some families of graphs the precise values of these parameters are proved. (c) 2006 Elsevier B.V. All rights reserved.**Description:**C1**Description:**2003004909

- Nguyen, Minh Hoang, Miller, Mirka, Gimbert, Joan

**Authors:**Nguyen, Minh Hoang , Miller, Mirka , Gimbert, Joan**Date:**2007**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 307, no. 7-8 (2007), p. 964-970**Full Text:**false**Reviewed:****Description:**The Moore bound for a directed graph of maximum out-degree d and diameter k is M**Description:**C1**Description:**2003005024

Calculating the extremal number ex (v ; {C3, C4, ..., Cn})

- Tang, Jianmin, Lin, Yuqing, Miller, Mirka

**Authors:**Tang, Jianmin , Lin, Yuqing , Miller, Mirka**Date:**2006**Type:**Text , Journal article**Relation:**Electronic Notes in Discrete Mathematics Vol. 27, no. (2006), p. 101-102**Full Text:**false**Reviewed:****Description:**This paper introduces and analyzes a parallel method of simulated annealing. Borrowing from genetic algorithms, an effective combination of simulated annealing and genetic algorithms, called parallel recombinative simulated annealing, is developed. This new algorithm strives to retain the desirable asymptotic convergence properties of simulated annealing, while adding the populations approach and recombinative power of genetic algorithms. The algorithm iterates a population of solutions rather than a single solution, employing a binary recombination operator as well as a unary neighborhood operator. Proofs of global convergence are given for two variations of the algorithm. Convergence behavior is examined, and empirical distributions are compared to Boltzmann distributions. Parallel recombinative simulated annealing is amenable to straightforward implementation on SIMD, MIMD, or shared-memory machines. The algorithm, implemented on the CM-5, is run repeatedly on two deceptive problems to demonstrate the added implicit parallelism and faster convergence which can result from larger population sizes.**Description:**C1

Characterization of eccentric digraphs

- Gimbert, Joan, Lopez, Nacho, Miller, Mirka, Ryan, Joe

**Authors:**Gimbert, Joan , Lopez, Nacho , Miller, Mirka , Ryan, Joe**Date:**2006**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 306, no. 2 (2006), p. 210-219**Full Text:**false**Reviewed:****Description:**The eccentric digraph ED(G) of a digraph G represents the binary relation, defined on the vertex set of G, of being 'eccentric'; that is, there is an arc from u to v in ED(G) if and only if v is at maximum distance from u in G. A digraph G is said to be eccentric if there exists a digraph H such that G=ED(H). This paper is devoted to the study of the following two questions: what digraphs are eccentric and when the relation of being eccentric is symmetric. We present a characterization of eccentric digraphs, which in the undirected case says that a graph G is eccentric iff its complement graph G is either self-centered of radius two or it is the union of complete graphs. As a consequence, we obtain that all trees except those with diameter 3 are eccentric digraphs. We also determine when ED(G) is symmetric in the cases when G is a graph or a digraph that is not strongly connected. Crown Copyright © 2006 Published by Elsevier B.V. All rights reserved.**Description:**C1**Description:**2003001601

Are you sure you would like to clear your session, including search history and login status?