Maximum Degree

The structure of a large network (graph) can often be revealed by partitioning it into smaller and possibly more dense sub-networks that are easier to handle. One of such decompositions is based on “k-cores”, proposed in 1983 by Seidman. Together with connectivity components, cores are one among few concepts that provide efficient decompositions of large graphs and networks. In this

Many hard algorithmic problems dealing with graphs, circuits, formulas and constraints admit polynomial-time upper bounds if the underlying graph has small treewidth. The same problems often encourage reducing the maximal degree of vertices to simplify theoretical arguments or address practical concerns. Such degree reduction can be performed through a sequence of splittings of vertices, resulting in an expansion of the

A set S of vertices in a graph G(V, E) is called a dominating set if every vertex v ∈ V is either an element of S or is adjacent to an element of S. A set S of vertices in a graph G(V, E) is called a total dominating set if every vertex v ∈ V is adjacent to an element of S. The domination number of a graph G denoted by γ(G) is the minimum cardinality of a dominating set in G. Respectively the total domination number of a graph G denoted by γt(G) is the minimum cardinality of a total dominating set in G. An upper bound for γt(G) which has been achieved by Cockayne and et al. in [1] is: for any graph G with no isolated vertex and maximum degree Δ(G) and n vertices, γt(G) ≤ n − Δ(G )+1 . Here we characterize bipartite graphs and trees which achieve this upper bound. Further we present some another upper and lower bounds for γt(G). Also, for circular complete graphs, we determine the value of γt(G).

Carboxymetyl celluloses (CMCs) were prepared from both cotton linter cellulose and spruce sulfite specialty cellulose samples. The resulting carboxymethyl celluloses were investigated by viscometric measurements and by 1 H- and 13C-NMR spectroscopy. There was no detectable difference between the two types of raw material, neither in viscosity stability during carboxymethylation, nor in the extent of the substitution reaction. Under the

One of the most popular cured rubbers used in industrial applications is polybutadiene rubber (BR) and frequently its network structure, in the cured state, is studied by means of swelling in a solvent. Normally, toluene is used as solvent in this test. In order to estimate the crosslink density from the equilibrium volume fraction of rubber in the swollen state, the correct evaluation of the Flory–Huggins interaction parameter χ is necessary. This work covers the swelling behaviour of two types of cured BR in toluene. The rubbers used have sulphur and accelerator in their composition and were vulcanized at 433 K at different times in order to obtain several network structures and crosslink densities. The crosslink densities were evaluated from uniaxial stress-strain data measured at room temperature and analysed in the frame of the conformational tube model. Using this information and the swelling measurements in the frame of the Flory–Rehner relationship, a relationship between χ and vr, the polymer volume fraction at equilibrium (maximum) degree of swelling was established for the cured BR/toluene system. It was found that χ is not a constant but depends on the crosslink density of the sample.

Feature selection has become very important research in musical instruments sounds for handling the problem of ‘curse of dimensionality’. In literature, various feature selection techniques have been applied in this domain focusing on Western musical instruments sounds. However, study on feature selection using rough sets of non-Western musical instruments sounds including Malay Traditional musical instruments is inadequate and still needs an intensive research. Thus, in this paper, an alternative feature selection technique using rough set theory based on Maximum Degree of dependency of Attributes (MDA) technique proposed by [8] for Traditional Malay musical instruments sounds is proposed. The modeling process comprises eight phases: data acquisition, sound editing, data representation, feature extraction, data discretization, data cleansing, feature selection using proposed technique and feature validation via classification. The results show that the highest classification accuracy of 99.82% was achieved from the best 17 features with 1-NN classifier.

Research in VLSI placement, an NP-hard problem, has branched in two different directions. The first one employs iterative heuristics with many tunable parameters to produce a near-optimal solution but without theoretical guarantee on its quality. The other one considers ...

In this paper, we propose a new hash function based on RC4 and we call it RC4-Hash. This proposed hash function produces variable length hash output from 16 bytes to 64 bytes. Our RC4-Hash has several advantages over many popularly known hash functions. Its efficiency is comparable with widely used known hash function (e.g., SHA-1). Seen in the light of recent attacks on MD4, MD5, SHA-0, SHA-1 and on RIPEMD, there is a serious need to consider other hash function design strategies. We present a concrete hash function design with completely new internal structure. The security analysis of RC4-Hash can be made in the view of the security analysis of RC4 (which is well studied) as well as the attacks on different hash functions. Our hash function is very simple and rules out all possible generic attacks. To the best of our knowledge, the design criteria of our hash function is different from all previously known hash functions. We believe our hash function to be secure and will appreciate security analysis and any other comments.

Graph pebbling is a network model for studying whether or not a given supply of discrete pebbles can satisfy a given demand via pebbling moves. A pebbling move across an edge of a graph takes two pebbles from one endpoint and places one pebble at the other endpoint; the other pebble is lost in transit as a toll. It has been shown that deciding whether a supply can meet a demand on a graph is NP-complete. The pebbling number of a graph is the smallest t such that every supply of t pebbles can satisfy every demand of one pebble. Deciding if the pebbling number is at most k is \Pi_2^P-complete. In this paper we develop a tool, called the Weight Function Lemma, for computing upper bounds and sometimes exact values for pebbling numbers with the assistance of linear optimization. With this tool we are able to calculate the pebbling numbers of much larger graphs than in previous algorithms, and much more quickly as well. We also obtain results for many families of graphs, in many cases by hand, with much simpler and remarkably shorter proofs than given in previously existing arguments (certificates typically of size at most the number of vertices times the maximum degree), especially for highly symmetric graphs. Here we apply the Weight Function Lemma to several specific graphs, including the Petersen, Lemke, 4th weak Bruhat, Lemke squared, and two random graphs, as well as to a number of infinite families of graphs, such as trees, cycles, graph powers of cycles, cubes, and some generalized Petersen and Coxeter graphs. This partly answers a question of Pachter, et al., by computing the pebbling exponent of cycles to within an asymptotically small range. It is conceivable that this method yields an approximation algorithm for graph pebbling.