38207892
On the Relations Between Arboricity and Independent Number Or Covering Number
In this paper, the following results are obtained: a(G) + β(G) ⩽ p + 1, ⌈p2⌉ ⩽ a(G)β(G), ⌈p2⌉ ⩽ a′(G) + gb′(G) ⩽ pa′(G) + α′(G) ⩽ 2⌈p2⌉ (δ ⩽ 1) and all bounds are sharp, where p = ¦V(G)¦, ⌈x⌉ denotes the smallest integer greater than or equal to x, a(G) is the vertex arboricity, a′(G) is the edge arboricity, α′(G) is the edge covering number, β(G) is the vertex independent number, β′(G) is the edge independent number, and δ is the minimum degree of G.
6641485
On total covers of graphs
A total cover of a graph G is a subset of V(G)∪E(G) which covers all elements of V(G)∪E(G). The total covering number α2(G) of a graph G is the minimum cardinality of a total cover in G. In [1], it is proven that α2(G)⩽[n2] for a connected graph G of order n. Here we consider the extremal case and give some properties of connected graphs which have a total covering number [n2]. We prove that such a graph with even order has a 1-factor and such a graph with odd order is factor-critical.
17919993
A Note on the Edge-Connectivity of Cages
A (k; g)-graph is a k-regular graph with girth g. A (k; g)-cage is a (k; g)-graph with the smallest possible number of vertices. In this paper we prove that (k; g)cages are k-edge-connected if k ≥ 3 and g is odd.
31774377
Factors in graphs with odd-cycle property
Abstract We present some conditions for the existence of a ( g , f )-factor or a ( g , f )-parity factor in a graph G with the odd-cycle property that any two odd cycles of G either have a vertex in common or are joined by an edge.
206571042
An Upper Bound for the Independent Domination Number
Let G be a simple graph of order n and minimum degree ?. The independent domination number i(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. In this paper, we show that i(G)?n+2??2n?. Thus a conjecture of Favaron is settled in the affirmative.
37643061
Adjacent strong edge coloring of graphs
Abstract For a graph G ( V , E ), if a proper k -edge coloring ƒ is satisfied with C ( u ) ≠ C ( v ) for uv ∈ E ( G ), where C(u) = {ƒ(uv) | uv ∈ E} , then ƒ is called k-adjacent strong edge coloring of G , is abbreviated k-ASEC , and χ ′ as ( G ) = min { k | k - ASEC of G } is called the adjacent strong edge chromatic number of G . In this paper, we discuss some properties of χ′ as ( G ), and obtain the χ′ as ( G ) of some special graphs and present a conjecture: if G are graphs whose order of each component is at least six, then χ ′ as ( G ) ≤ Δ ( G ) + 2, where Δ( G ) is the maximum degree of G .
16584684
Diagonal Flips in Labelled Planar Triangulations
Abstract. A classical result of Wagner states that any two (unlabelled) planar triangulations with the same number of vertices can be transformed into each other by a finite sequence of diagonal flips. Recently Komuro gives a linear bound on the maximum number of diagonal flips needed for such a transformation. In this paper we show that any two labelled triangulations can be transformed into each other using at most O(nlogn) diagonal flips. We will also show that any planar triangulation with n>4 vertices has at least n− 2 flippable edges. Finally, we prove that if the minimum degree of a triangulation is at least 4, then it contains at least 2n + 3 flippable edges. These bounds can be achieved by an infinite class of triangulations.
13962172
Diversity in multimedia information retrieval research
Multimedia information retrieval is a highly diverse field. A variety of data types, research problems,methodologies are involved.Researchers in the field come from very different disciplines, ranging from mathematical and physical sciences, computational sciences and engineering, to application domains. The panel, consisting of highly visible active researchers from both academia and the industry,opens a discussion on the importance of diversity to the healthy growth of the field. This paper records their opinions expressed at the panel.
40574141
Finding similar consensus between trees: an algorithm and a distance hierarchy
Abstract The problem of finding this similar consensus (also known as the largest approximately common substructures) of two trees arises in many pattern recognition applications. This paper presents a dynamic programming algorithm to solve the problem based on the distance measure originated from Tanaka and Tanaka. The algorithm runs as fast as the best-known algorithm for comparing two trees using Tanaka's distance measure when the allowed distance between the common substructures is a constant independent of the input trees. In addition, we establish a hierarchy among Tanaka's distance measure and three other edit-based distance measures published in the literature.
18868983
Mobility-Pattern Based Localization Update Algorithms for Mobile Wireless Sensor Networks
In mobile wireless sensor networks, sensors move in the monitored area at any direction and at any speed. Unlike many other networking hosts, sensor nodes do not have global addresses. Very often they are identified by using a location-based addressing scheme. Therefore, it is important to have the knowledge of the sensor location indicating where the data came from. In this paper, we design three mobility-pattern based localization update algorithms. Specifically, we divide sensor movements into three states, Pause, Linear, and Random. Each state adopts different localization update algorithms. Analytical and simulation results are provided to study the localization cost and location accuracy of the proposed localization-update algorithm in different mobility patterns. The analysis to these results indicates that the localization cost is minimized and the location accuracy is improved.
45865876
Graph theoretic characterization and reliability of the generalized Boolean n-cube network
In this paper, a general class of Boolean n-cube structures is investigated. The interconnection is based on a mixed radix number system which results in a variety of generalized Boolean n-cube structures for a given number of processors N = x·2y, where x and y are positive integers. A number of interesting properties of the network are revealed. By a constructive method, the node connectivity of this network is found. Finally, we show that the graph is super-λ and is an optimal reliable structure for interconnection networks.