27950545
On Vertex-Triads in 3-Connected Binary Matroids
A cocircuit C* in a matroid M is said to be non-separating if and only if M∖C*, the deletion of C* from M, is connected. A vertex-triad in a matroid is a three-element non-separating cocircuit. Non-separating cocircuits in binary matroids correspond to vertices in graphs. Let C be a circuit of a 3-connected binary matroid M such that ∣E(M)∣≥4 and, for all elements x of C, the deletion of x from M is not 3-connected. We prove that C meets at least two vertex-triads of M. This gives direct binary matroid generalizations of certain graph results of Halin, Lemos, and Mader. For binary matroids, it also generalizes a result of Oxley. We also prove that a minimally 3-connected binary matroid M which has at least four elements has at least ½r*(M)+1 vertex-triads, where r*(M) is the corank of the matroid M. An immediate consequence of this result is the following result of Halin: a minimally 3-connected graph with n vertices has at least 2n+6/5 vertices of degree three. We also generalize Tutte's Triangle Lemma for general matroids.
17076833
On the Structure of 3-connected Matroids and Graphs
An element e of a 3 -connected matroid M is essential if neither the deletionM\e nor the contraction M/e is 3 -connected. Tutte?s Wheels and Whirls Theorem proves that the only 3 -connected matroids in which every element is essential are the wheels and whirls. In this paper, we consider those 3 -connected matroids that have some non-essential elements, showing that every such matroid M must have at least two such elements. We prove that the essential elements of M can be partitioned into classes where two elements are in the same class if M has a fan, a maximal partial wheel, containing both. We also prove that if an essential element e of M is in more than one fan, then that fan has three or five elements; in the latter case, e is in exactly three fans. Moreover, we show that if M has a fan with 2 k or 2 k+ 1 elements for some k? 2, then M can be obtained by sticking together a (k+ 1)-spoked wheel and a certain 3 -connected minor of M. The results proved here will be used elsewhere to completely determine all 3 -connected matroids with exactly two non-essential elements.
44791044
A Generalization of a Theorem of Dirac
In this paper, we give a generalization of a well-known result of Dirac that given any k vertices in a k-connected graph where k?2, there is a circuit containing all of them. We also generalize a result of Haggkvist and Thomassen. Our main result partially answers an open matroid question of Oxley.
31035436
Contractible Elements in Graphs and Matroids
Let G be a simple 3-connected graph with at least five vertices. Tutte [13] showed that G has at least one contractible edge. Thomassen [11] gave a simple proof of this fact and showed that contractible edges have many applications. In this paper, we show that there are at most $\frac{|V(G)|}{5}$ vertices that are not incident to contractible edges in a 3-connected graph G. This bound is best-possible. We also show that if a vertex v is not incident to any contractible edge in G, then v has at least four neighbours having degree three, and each such neighbour is incident to exactly two contractible edges. We give short proofs of several results on contractible edges in 3-connected graphs as well. We also study the contractible elements for k-connected matroids. We partially solve an open problem for regular matroids.
38263878
A Longest Cycle Version of Tutte's Wheels Theorem
An edgeeof a minimally 3-connected graphGis non-essential if and only if the graph obtained by contractingefromGis both 3-connected and simple. Suppose thatGis not a wheel. Tutte's Wheels Theorem states thatGhas at least one non-essential edge. We show that each longest cycle ofGcontains at least two non-essential edges. Moreover, each cycle ofGwhose edge set is not contained in a fan contains at least two non-essential edges. We characterize the minimally 3-connected graphs which contain a longest cycle containing exactly two non-essential edges.
6756167
MAC-SCC: medium access control with a separate control channel for multihop wireless networks
The recent research has shown that the basic RTS/CTS approach is not efficient in multihop wireless networks. In this paper, we propose a novel medium access control protocol with a separate control channel (MAC-SCC). A distinct feature of MAC-SCC (compared with other multichannel MAC protocols) is to use two Network Allocation Vectors (NAVs) for the data channel and the control channel, respectively. The transmission of the next data frame can be pre-determined during the current transmission via the separate control channel, and thus the frame collision probability and bandwidth wasted during backoff can be reduced. The system throughput is quantified via simulation. The results show that MAC-SCC yields a throughput gain up to 60% under high traffic load and has a significant lower link failure probability.
12829985
Type-2 Fuzzistics for Symmetric Interval Type-2 Fuzzy Sets: Part 2, Inverse Problems
In Part 1 of this two-part paper, we bounded the centroid of a symmetric interval type-2 fuzzy set (T2 FS), and consequently its uncertainty, using geometric properties of its footprint of uncertainty (FOU). We then used these bounds to solve forward problems, i.e., to go from parametric interval T2 FS models to data. The main purpose of the present paper is to formulate and solve inverse problems, i.e., to go from uncertain data to parametric interval T2 FS models, which we call type-2 fuzzistics. Given interval data collected from people about a phrase, and the inherent uncertainties associated with that data, which can be described statistically using the first- and second-order statistics about the end-point data, we establish parametric FOUs such that their uncertainty bounds are directly connected to statistical uncertainty bounds. These results should find applicability in computing with words
16314153
A New Fragile Mesh Watermarking Algorithm for Authentication
In this paper, we propose a new fragile watermarking algorithm based on the global characteristics of the mesh geometry to authenticate 3D mesh models. In our method, a sequence of data bits is adaptively embedded into the mesh model by properly adjusting the vertex positions, and the bit information can be blindly extracted from the watermarked mesh model using a key. The embedding process is adaptive to the mesh model so that the watermarked mesh is perceptually indistinguishable from the original. We show that the embedded watermark is invariant to affine transformation but sensitive to other operations. Besides, the embedding strength is adjustable and can be controlled to a certain extent that even a trivial tampering with the watermarked mesh would lead the watermark signal to change. Therefore, unauthorized modifications of the mesh models can be detected and estimated.