Commentary on Section 264 of ITAA 1936: commissioner may require information and evidence
Dabner, Justin
2007-01-01
Search results
80 records were found.
Let Cone(G), Int.Cone(G) and Lat(G) be the cone, the integer cone and the lattice of the incidence vectors of the circuits of graph G. A good range is a set K of natural numbers such that the intersection of Cone(G), Lat(G) and K^E is contained in Int.Cone(G) for every graph G=(V,E). We give a counterexample to a conjecture of Goddyn [ Goddyn, L.A.: Cones, Lattices and Hilbert Bases of Circuits and Perfect Matchings. Contemporary Mathematics 147, 419--439 (1993)] stating that N\{1} is a good range.
We give a short proof of the following basic fact in matching theory: in a bipartite graph the maximum size of a matching equals the minimum size of a node cover.
We give a simple, self-contained proof of the following basic fact in matching theory: every bipartite regular multigraph is factorizable.
A circuit decomposition of a graph G=(V,E) is a partition of E into circuits. A decomposition is said even if all its circuits have even length. We give a negative answer to a question posed by Jackson asking whether K_5 is the only 4-connected eulerian graph with an even number of edges but no even circuit decomposition.
A simple graph is P_4-indifferent if it admits a total order < on its nodes such that every chordless path with nodes a,b,c,d and edges ab,bc,cd has ab>c>d. P_4-indifferent graphs generalize indifferent graphs and are perfectly orderable. Recently, Hoang, Maffray and Noy gave a characterization of P_4-indifferent graphs in terms of forbidden induced subgraphs. We clarify their proof and describe a linear time algorithm to recognize P_4-indifferent graphs. When the input is a P_4-indifferent graph, then the algorithm computes an order < as above.
Mader proved that every loopless undirected graph contains a pair (u,v) of nodes such that the star of v is a minimum cut separating u and v. Nagamochi and Ibaraki showed that the last two nodes of a "max-back order" form such a pair and used this fact to develop an elegant min-cut algorithm. M. Queyranne extended this approach to minimize symmetric submodular functions. With the help of a short and simple proof, here we show that the same algorithm works for an even more general class of set functions.
The Standard Generalized Markup Language (SGML) and the Extensible Markup Language (XML) allow authors to better transmit the semantics in their documents by explicitly specifying the relevant structures in a document or class of documents by means of document type definitions (DTDs. Several authors have proposed to regard DTDs as extended context-free grammars expressed in a notation similar to extended Backus--Naur form. In addition, the SGML standard allows the semantics of content models (the right-hand side of productions) to be modified by exceptions. Inclusion exceptions allow named elements to appear anywhere within the content of a content model, and exclusion exceptions preclude named elements from appearing in the content of a content model. Since XML does not allow exceptions, the problem of exception removal has received m...
An r-graph is any graph that can be obtained as a conic combination of its own 1-factors. An r-graph G=(V,E) is said indecomposable when its edge set E cannot be partitioned as the disjoint union of sets E_1 and E_2 so that (V,E_i) is an r_i-graph for i=1,2 and for some r_1, r_2. We give an indecomposable r-graph for every integer r >= 4. This answers a question raised in 1: [ P.D. Seymour, On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte. Proceedings of the London Mathematical Society, Vol. 38, 423--460, (1979)] and 2: [ P.D. Seymour, Some unsolved problems on one-factorizations of graphs. Graph Theory and Related Topics, J.A. Bondy and U.S.R. Murty, Eds., 367--368, Academic Press, New York, 1979] and has interesting consequences for the Schrijver System of the T-cut polyhedron to be given in 3: [ R. Rizzi, ...
Let G be an undirected graph. The Chinese Postman Problem (CPP) asks for a shortest postman tour in G, i.e. a closed walk using each edge at least once. The Shortest Cycle Cover Problem (SCC) asks for a family C of circuits of G such that each edge is in some circuit of C and the total length of all circuits in C is as small as possible. Clearly, an optimal solution of CPP can not be greater than a solution of SCC. A graph G has the CPP=SCC property when the solutions to the two problems have the same value. Graph G is said to have the cycle cover property if for every Eulerian 1,2-weighting w: E(G) --> {1,2} there exists a family C of circuits of G such that every edge e is in precisely w_e circuits of C. The cycle cover property implies the CPP=SCC property. We give a counterexample to a conjecture of Zhang stating the equivalence of...
We give a simple algorithm for finding a minimum T-cut. At present, all known efficient algorithms for this problem go through the computation of a Gomory-Hu tree. While our algorithm bases on the same fundamental properties of uncrossing as the previous methods, still it provides an ad-hoc solution. This solution is easier to implement and faster to run. Our results extend to the whole of symmetric submodular functions.
