All (k;g)-cages are edge-superconnected
- Authors: Lin, Yuqing , Miller, Mirka , Balbuena, Camino , Marcote, Xavier
- Date: 2006
- Type: Text , Journal article
- Relation: Networks Vol. 47, no. 2 (2006), p. 102-110
- Full Text: false
- Reviewed:
- Description: A (k;g)-cage is k-regular graph with girth g and with the least possible number of vertices. In this article we prove that (k;g)-cages are edge-superconnected if g is even. Earlier, Marcote and Balbuena proved that (k;g)-cages are edge-superconnected if g is odd [Networks 43 (2004), 54-59]. Combining our results, we conclude that all (k;g)-cages are edge-superconnected. © 2005 Wiley Periodicals, Inc.
- Description: C1
- Description: 2003001830
Calculating the extremal number ex (v ; {C3, C4, ..., Cn})
- 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
- 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
Consecutive magic graphs
- Authors: Balbuena, Camino , Barker, Ewan , Lin, Yuqing , Miller, Mirka , Sugeng, Kiki Ariyanti
- Date: 2006
- Type: Text , Journal article
- Relation: Discrete Mathematics Vol. 306, no. 16 (2006), p. 1817-1829
- Full Text: false
- Reviewed:
- Description: Let G be a graph of order n and size e. A vertex-magic total labeling is an assignment of the integers 1, 2, ..., n + e to the vertices and the edges of G, so that at each vertex, the vertex label and the labels on the edges incident at that vertex, add to a fixed constant, called the magic number of G. Such a labeling is a-vertex consecutive magic if the set of the labels of the vertices is { a + 1, a + 2, ..., a + n }, and is b-edge consecutive magic if the set of labels of the edges is { b + 1, b + 2, ..., b + e }. In this paper we prove that if an a-vertex consecutive magic graph has isolated vertices then the order and the size satisfy (n - 1)
- Description: C1
- Description: 2003001604
Divisibility conditions in almost Moore digraphs with selfrepeats
- Authors: Teska, Jakub , Kuzel, Roman , Miller, Mirka
- Date: 2006
- Type: Text , Journal article
- Relation: Electronic Notes in Discrete Mathematics Vol. 24, no. (2006), p. 161-163
- Full Text: false
- Reviewed:
- Description: Moore digraph is a digraph with maximum out-degree d, diameter k and order Md, k = 1 + d + ... + dk. Moore digraphs exist only in trivial cases if d = 1 (i.e., directed cycle Ck) or k = 1 (i.e., complete symmetric digraph). Almost Moore digraphs are digraphs of order one less than Moore bound. We shall present new properties of almost Moore digraphs with selfrepeats from which we prove nonexistence of almost Moore digraphs for some k and d. © 2006 Elsevier B.V. All rights reserved.
- Description: C1
Face antimagic labelings of prisms
- Authors: Sugeng, Kiki Ariyanti , Miller, Mirka , Baca, Martin
- Date: 2006
- Type: Text , Journal article
- Relation: Utilitas Mathematica Vol. 71, no. (Nov 2006), p. 269-286
- Full Text: false
- Reviewed:
- Description: This paper deals with the problem of labeling the vertices, edges and faces of a plane graph in such a way that the label of a face and labels of vertices and edges surrounding that face add up to a weight of that face. A labeling of a plane graph is called d-antimagic if for every number s, the s-sided face weights form an arithmetic progression of difference d. In this paper, we investigate d-antimagic labelings for prism for d is an element of {7, 8, 9, 10, 12, 14, 15, 16, 17, 18, 20, 21, 24, 26,27,30,36).
- Description: C1
Knowledge based regulation of statistical databases
- Authors: Mishra, Vivek , Stranieri, Andrew , Miller, Mirka , Ryan, Joe
- Date: 2006
- Type: Text , Journal article
- Relation: WSEAS Transactions on Information Science and Applications Vol. 3, no. 2 (2006), p. 239-244
- Full Text: false
- Reviewed:
- Description: A statistical database system is a system that contains information about individuals, companies or organisations that enables authorized users to retrieve aggregate statistics such as mean and count. The regulation of a statistical database involves limiting the use of the database so that no sequence of queries is sufficient to infer protected information about an individual. The database is said to be compromised when individual confidential information is obtained as a result of a statistical query. Devices to protect against compromise include adding noise to the data or restricting a query. While effective, these techniques are sometimes too strong in that legitimate compromises for reasons of public safety are always blocked. Further, a statistical database can be often be compromised with some knowledge about the database attributes (working knowledge), the real world (supplementary knowledge) or the legal system (legal knowledge). In this paper we illustrate that a knowledge based system that represents working, supplementary and legal knowledge can contribute to the regulation of a statistical database.
- Description: C1
- Description: 2003001608
Managing privacy, trust, security, and context relationships using weighted graph representations
- Authors: Skinner, Geoff , Miller, Mirka
- Date: 2006
- Type: Text , Journal article
- Relation: Transactions on Information Science and Applications Vol. 3, no. 2 (2006), p. 283-290
- Full Text: false
- Reviewed:
- Description: Determining who has access to personal data is an ongoing problem facing information system entities. The establishment of trust and its representation for known and unknown entities within the system further complicates access control rights allocation. One unique solution is through the application of graph representation to aid in the identification and management of privacy, trust and security requirements. Graphs provide a much better mental map than would textual information. In this paper we use graphs to represent informational relations concerning trust levels between entities for privacy and security requirements.
- Description: C1
- Description: 2003001598
Multipartite Moore digraphs
- Authors: Fiol, M. A. , Gimbert, Joan , Miller, Mirka
- Date: 2006
- Type: Text , Journal article
- Relation: Linear Algebra and Its Applications Vol. 419, no. 1 (2006), p. 234-250
- Full Text: false
- Reviewed:
- Description: We derive some Moore-like bounds for multipartite digraphs, which extend those of bipartite digraphs, under the assumption that every vertex of a given partite set is adjacent to the same number δ of vertices in each of the other independent sets. We determine when a multipartite Moore digraph is weakly distance-regular. Within this framework, some necessary conditions for the existence of a r-partite Moore digraph with interpartite outdegree δ > 1 and diameter k = 2m are obtained. In the case δ = 1, which corresponds to almost Moore digraphs, a necessary condition in terms of the permutation cycle structure is derived. Additionally, we present some constructions of dense multipartite digraphs of diameter two that are vertex-transitive.
- Description: C1
- Description: 2003002157
On optimum summable graphs
- Authors: Miller, Mirka , Koh, K. M. , Smyth, W. F. , Wang, Yan
- Date: 2006
- Type: Text , Journal article
- Relation: AKCE International Journal of Graphs and Combinatorics Vol. 3, no. 1 (2006), p. 45-57
- Full Text: false
- Reviewed:
- Description: C1
- Description: 2003001922
On the degrees of a strongly vertex-magic graph
- Authors: Balbuena, Camino , Barker, Ewan , Das, K. C. , Lin, Yuqing , Miller, Mirka , Ryan, Joe , Slamin, , Sugeng, Kiki Ariyanti , Tkac, M.
- Date: 2006
- Type: Text , Journal article
- Relation: Discrete Mathematics Vol. 306, no. 6 (2006), p. 539-551
- Full Text: false
- Reviewed:
- Description: Let G=(V,E) be a finite graph, where |V|=n≥2 and |E|=e≥1. A vertex-magic total labeling is a bijection λ from V∪E to the set of consecutive integers {1,2,...,n+e} with the property that for every v∈V, λ(v)+∑w∈N(v)λ(vw)=h for some constant h. Such a labeling is strong if λ(V)={1,2,...,n}. In this paper, we prove first that the minimum degree of a strongly vertex-magic graph is at least two. Next, we show that if 2e≥10n2-6n+1, then the minimum degree of a strongly vertex-magic graph is at least three. Further, we obtain upper and lower bounds of any vertex degree in terms of n and e. As a consequence we show that a strongly vertex-magic graph is maximally edge-connected and hamiltonian if the number of edges is large enough. Finally, we prove that semi-regular bipartite graphs are not strongly vertex-magic graphs, and we provide strongly vertex-magic total labeling of certain families of circulant graphs. © 2006 Elsevier B.V. All rights reserved
- Description: C1
- Description: 2003001603
Structure of repeat cycles in almost Moore digraphs with selfrepeats and diameter 3
- Authors: Miller, Mirka , Baskoro, Edy , Cholily, Yus Mochamad
- Date: 2006
- Type: Text , Journal article
- Relation: Bulletin of the Institute of Combinatorics and its Applications Vol. 46, no. (2006), p. 99-109
- Full Text: false
- Reviewed:
- Description: C1
- Description: 2003001829
Super edge-antimagic total labeling
- Authors: Sugeng, Kiki Ariyanti , Miller, Mirka , Baca, Martin
- Date: 2006
- Type: Text , Journal article
- Relation: Utilitas Mathematica Vol. 71, no. (2006), p. 131-141
- Full Text: false
- Reviewed:
- Description: A (p, q)-graph G is (a, d)-edge-antimagic total if there exists a bijective function f : V(G) ∪ E(G) → {1,2,...,p + q} such that the edge-weights w(uv) = f(u) + f(v) + f(uv), uv ∈ E(G), form an arithmetic progression starting from a and having common difference d. Moreover, G is said to be super (a, d)-edge-antimagic total if f(V(G)) = {1,2,..., p}. In this paper we study the super (a,d)-edge-antimagic total properties of certain classes of graphs, including ladders, generalized prisms and antiprisrns.
- Description: C1
- Description: 2003001596
Survey of edge antimagic labelings of graphs
- Authors: Miller, Mirka , Baca, Martin , Baskoro, Edy , Ryan, Joe , Simanjuntak, Rinovia , Sugeng, Kiki Ariyanti
- Date: 2006
- Type: Text , Journal article
- Relation: Journal of Indonesian Mathematical Society, MIHMI Vol. 12, no. 1 (2006), p. 113-130
- Full Text: false
- Reviewed:
- Description: C1
- Description: 2003001600
Two new families of large compound graphs
- Authors: Marti, J. Gomez , Miller, Mirka
- Date: 2006
- Type: Text , Journal article
- Relation: Networks Vol. 47, no. 3 (2006), p. 140-146
- Full Text: false
- Reviewed:
- Description: A question of special interest in graph theory is the design of large graphs. Specifically, we want to find constructions of graphs with order as large as possible for a given degree A and diameter D. Two generalizations of two large compound graphs are proposed in this article. Three particular cases of these families of graphs presented here allow us to improve the order for the entries (15, 7), (13, 10), and (15, 10) in the table of the largest known (Δ, D)-graphs. © 2006 Wiley Periodicals, Inc.
- Description: C1
- Description: 2003001599
(a,d)-edge-antimagic total labelings of caterpillars
- Authors: Miller, Mirka , Sugeng, Kiki Ariyanti , Slamin, , Baca, Martin
- Date: 2005
- Type: Text , Journal article
- Relation: Combinatorial Geometry and Graph Theory, LNCS 3330, Lecture Notes in Computer Science, Indonesia-Japan Joint Conference IJCCGGT 2003, Bandung, Indonesia, September 2003, Revised Selected Papers Vol. 3330, no. (2005), p. 169-180
- Full Text: false
- Reviewed:
- Description: For a graph G = (V,E), a bijection g from V (G)∪E(G) into {1, 2, ..., |V (G)|+|E(G)|} is called (a, d)-edge-antimagic total labeling of G if the edge-weights w(xy) = g(x) + g(y) + g(xy), xy ∈ E(G), form an arithmetic progression with initial term a and common difference d. An (a, d)-edge-antimagic total labeling g is called super (a, d)-edge-antimagic total if g(V (G)) = {1, 2, ..., |V (G)|}. We study super (a, d)-edge-antimagic total properties of stars Sn and caterpillar Sn1,n2,...,nr .
- Description: C1
- Description: 2003001412
All (k;g)-cages are k-edge-connected
- Authors: Lin, Yuqing , Miller, Mirka , Rodger, Chris
- Date: 2005
- Type: Text , Journal article
- Relation: Journal of Graph Theory Vol. 48, no. 3 (2005), p. 219-227
- 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 prove that (k;g)-cages are k-edge-connected if g is even. Earlier, Wang, Xu, and Wang proved that (k;g)-cages are k-edge-connected if g is odd. Combining our results, we conclude that the (k;g)-cages are k-edge-connected. © 2005 wiley Periodicals, Inc.
- Description: C1
Antimagic valuations for the special class of plane graphs
- Authors: Baca, Martin , Baskoro, Edy , Miller, Mirka
- Date: 2005
- Type: Text , Journal article
- Relation: Lecture Notes in Computer Science Vol. 3350, no. (2005), p. 58-64
- Full Text: false
- Reviewed:
- Description: We deal with the problem of labeling the vertices, edges and faces of a special class of plane graphs with 3-sided internal faces 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 the weight of that face. These face weights then form an arithmetic progression with common difference d.
- Description: C1
- Description: 2003001410
Complete characterization of almost moore digraphs of degree three
- Authors: Baskoro, Edy , Miller, Mirka , Siran, Jozef , Sutton, Martin
- Date: 2005
- Type: Text , Journal article
- Relation: Journal of Graph Theory Vol. 48, no. 2 (2005), p. 112-126
- Full Text: false
- Reviewed:
- Description: It is well known that Moore digraphs do not exist except for trivial cases (degree 1 or diameter 1), but there are digraphs of diameter two and arbitrary degree which miss the Moore bound by one. No examples of such digraphs of diameter at least three are known, although several necessary conditions for their existence have been obtained. In this paper, we prove that digraphs of degree three and diameter k ≥ 3 which miss the Moore bound by one do not exist. © 2004 Wiley Periodicals, Inc.
- Description: C1
- Description: 2003000904
Conjectures and open problems on face antimagic evaluations of graphs
- Authors: Miller, Mirka , Baca, Martin , Baskoro, Edy , Cholily, Yus Mochamad , Jendrol, Stanislav , Lin, Yuqing , Ryan, Joe , Simanjuntak, Rinovia , Slamin, , Sugeng, Kiki Ariyanti
- Date: 2005
- Type: Text , Journal article
- Relation: Journal of Indonesian Mathematical Society MIHMI Vol. 11, no. 2 (2005), p. 175-192
- Full Text: false
- Reviewed:
- Description: C1
- Description: 2003001408