15233730
Circulant Distant Two Labeling and Circular Chromatic Number
Let G be a graph and d,d 0 be positive integers, d 0 d. An m-(d,d 0 )-circular distance two labeling is a function f : V (G) ! {0,1,2,···,m 1} such that |f(u) f(v)|m d if u and v are adjacent; and |f(u) f(v)|m d 0 if u and v are distance two apart, where |x|m := min{|x|,m| x|}. The minimum m such that there exists an m-(d,d 0 )-circular labeling for G is called the d,d0-number of G and denoted by d,d 0(G). The d,d 0-numbers for trees can be obtained by a first-fit algorithm. In this article, we completely determine the d,1-numbers for cycles. In addition, we show connections between generalized circular distance labeling and circular chromatic number.
45408024
Star Extremal Circulant Graphs
A graph is called star extremal if its fractional chromatic number is equal to its circular chromatic number (also known as the star chromatic number). We prove that members of a certain family of circulant graphs are star extremal. The result generalizes some known theorems of Sidorenko [Discrete Math., 91 (1991), pp. 215--217] and Gao and Zhu [Discrete Math., 152 (1996), pp. 147--156]. We show relations between circulant graphs and distance graphs and discuss their star extremality. Furthermore, we give counterexamples to two conjectures of Collins [SIAM J. Discrete Math., 11 (1998), pp. 330--339] on asymptotic independence ratios of circulant graphs.
16699960
Circular chromatic number for iterated Mycielski graphs
Abstract For a graph G , let M( G ) denote the Mycielski graph of G . The t th iterated Mycielski graph of G , M t ( G ), is defined recursively by M 0 ( G )= G , and M t ( G )=M(M t −1 ( G )) for t ⩾1. Let χ c ( G ) denote the circular chromatic number of G . We prove two main results: (1) If G has a universal vertex x , then χ c (M( G ))= χ (M( G )) if χ c (G−x)>χ(G)− 1 2 and G is not a star, otherwise χ c ( M (G))=χ( M (G))− 1 2 ; and (2) χ c (M t ( K m ))= χ (M t ( K m )) if m ⩾2 t −1 +2 t −2 and t ⩾2.
17515399
Sizes of Graphs with Fixed Orders and Spans for Circular-Distance-Two Labelings
A k-circular-distance-two labeling (or k-c-labeling) of a simple graph G is a vertex-labeling, using the labels 0, 1, 2, · · · , k − 1, such that the “circular difference” (mod k) of the labels for adjacent vertices is at least two, and for vertices of distance-two apart is at least one. The σ-number, σ(G), of a graph G is the minimum k of a k-c-labeling of G. For any given positive integers n and k, let G(n, k) denote the set of graphs G on n vertices and σ(G) = k. We determine the maximum size (number of edges) and the minimum size of a graph G ∈ G(n, k). Furthermore, we prove that for any value p between the maximum and the minimum size, there exists a graph G ∈ G(n, k) of size p. These results are analogues of the ones by Georges and Mauro [4] on distance-two labelings.
24184742
On Distance Two Labellings of Graphs
36089150
Hamiltonicity and circular distance two labellings
Abstract A k -circular distance two labelling (or k -c-labelling) of a graph G is a vertex-labelling such that the circular difference ( mod k ) of the labels is at least two for adjacent vertices, and at least one for vertices at distance two. Given G , denote σ(G) the minimum k for which there exists a k -c-labelling of G . Suppose G has n vertices, we prove σ(G)⩽n if G c is Hamiltonian; and σ(G)=n+p v (G c ) otherwise, where p v (G) is the path covering number of G . We give exact values of σ(G) for some families of graphs such that G c is Hamiltonian, and discuss injective k -c-labellings especially for joins and unions of graphs.
10993158
Efficient and Distributed Access Control for Sensor Networks
Sensor networks are often used to sense the physical world and provide observations for various uses. In hostile environments, it is critical to control the network access to ensure the integrity, availability, and at times confidentiality of the sensor data. This paper develops efficient methods for distributed access control in sensor networks. The paper starts with a baseline approach, which provides a more flexible and efficient way to enforce access control when compared with previous solutions. This paper then extends the baseline approach to enable privilege delegation, which allows a user to delegate its privilege to other users without using a trusted server, and broadcast query, which allows a user to access the network at a large scale efficiently. The privilege delegation and broadcast query are very useful in practice; none of the current solutions can achieve these two properties.
30709401
T-graphs and the channel assignment problem
Abstract T -colorings arose from the channel assignment problem in communications. Given a finite set T of non-negative integers, a T -coloring of a simple graph G is an assignment of a non-negative integer (channel) on every vertex of G , such that the difference of channels of two adjacent vertices does not fall in T . The T -span of G , denoted by sp T ( G ), is the minimum span among all possible T -colorings of G , where the span of a T -coloring is the difference between the largest and smallest channels used. This article applies T -graphs to explore the sets T that belong to these two collections: G = { T : greedy (or first-fit) algorithm provides T -spans for all complete graphs}, and E = { T : spt ( G ) = sp T ( K χ ( G ) ) for all graphs G , where χ is the chromatic number}. Given T , its T -graph has the vertex set of all non-negative integers so that two vertices are adjacent if their difference does not fall in T . We show that for any a ∈ Z + , the T -graph of aT is isomorphic to a disjoint product of a copies of the T -graph of T , where aT is the set obtained by multiplying every element of T by a . Based on this characterization, the following two results are attained. For any a ∈ Z + , T ∈ E if and only if aT ∈ E , and T ∈ G if and only if aT ∈ G . The second fact has been proven by Cozzens and Roberts (1991) from a different approach. We will completely solve the family of sets T = {0, s , s + 1,…, l } by providing a different proof of the fact T ∈ G (Tesman, 1989), and showing that T ∈ E if and only if l is a multiple of s . In addition, complete solutions for a more general family are obtained: for any a , s , l ∈ Z + with s ⩽ l , T = {0, as , a ( s + 1), a ( s + 2),…, al } ∪ A ∈ E , and T ϵ E if and only if l = ms for some m , where A ⊆{ as + 1, as + 2, …, al - 1}.
16371053
Discovering Useful Concept Prototypes for Classification Based on Filtering and Abstraction
The nearest-neighbor algorithm and its derivatives have been shown to perform well for pattern classification. Despite their high classification accuracy, they suffer from high storage requirement, computational cost, and sensitivity to noise. We develop anew framework, called ICPL (Integrated Concept Prototype Learner), which integrates instance-filtering and instance-abstraction techniques by maintaining a balance of different kinds of concept prototypes according to instance locality. The abstraction component, based on typicality, employed in our ICPL framework is specially designed for concept integration. We have conducted experiments on a total of 50 real-world benchmark data sets. We find that our ICPL framework maintains or achieves better classification accuracy and gains a significant improvement in data reduction compared with existing filtering and abstraction techniques as well as some existing techniques.
22528927
Solving the N-bit parity problem using neural networks
In this letter, a constructive solution to the N-bit parity problem is provided with a neural network that allows direct connections between the input layer and the output layer. The present approach requires no training and adaptation, and thus it warrants the use of the simple threshold activation function for the output and hidden layer neurons. It is previously shown that this choice of activation function and network structure leads to several solutions for the 3-bit parity problem obtained using linear programming. One of the solutions for the 3-bit parity problem is then generalized to obtain a solution for the N-bit parity problem using left floor N/2 right floor hidden layer neurons. It is shown that through the choice of a "staircase" type activation function, the left floor N/2 right floor hidden layer neurons can be further combined into a single hidden layer neuron.